Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2015/7/b/ii/solution

Choose a maximum matching and a minimum vertex cover . By Kőnig's theorem for bipartite matching, . Every edge of must have at least one endpoint in , because is a vertex cover. Distinct edges of the matching in a graph have disjoint endpoints, so these requirements already use at least distinct vertices of .
Since has exactly that many vertices, each edge of has exactly one endpoint in , and no vertex of lies outside the endpoints of . Thus selecting the unique endpoint in from each edge of produces precisely the vertex cover :
The argument also covers an edgeless graph: take both sets empty.

New to topics? Read the docs here!