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

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: