Past exam of the short options course of the University of Oxford / 2015 / 7 / b

A matching in a graph is a set of edges no two of which share a vertex. A cover here means a vertex cover: a set $C$ of vertices such that every edge has at least one endpoint in $C$. It is not an edge cover.

Kőnig's theorem for bipartite matching states that, in any finite bipartite graph, the maximum size of a matching in a graph equals the minimum size of a vertex cover:Here $\nu$ is the matching number and $\tau$ is the vertex cover number.

Choose a maximum matching $M$ and a minimum vertex cover $C$. By Kőnig's theorem for bipartite matching, $|M|=|C|$. Every edge of $M$ must have at least one endpoint in $C$, because $C$ is a vertex cover. Distinct edges of the matching in a graph have disjoint endpoints, so these requirements already use at least $|M|$ distinct vertices of $C$.

Since $C$ has exactly that many vertices, each edge of $M$ has exactly one endpoint in $C$, and no vertex of $C$ lies outside the endpoints of $M$. Thus selecting the unique endpoint in $C$ from each edge of $M$ produces precisely the vertex cover $C$:The argument also covers an edgeless graph: take both sets empty.

For every matching in a graph $M^{\prime }$ and every vertex cover $C^{\prime }$, the disjoint edges of $M^{\prime }$ need distinct covering vertices. ThereforeNow assume the assertion in part (ii). It supplies a matching in a graph $M$ and a vertex cover $C$ formed by choosing one endpoint of each edge of $M$. Because these edges are disjoint, the chosen endpoints are distinct, so $|C|=|M|$. By the definitions of maximum and minimum,Every inequality must be equality, proving Kőnig's theorem for bipartite matching: