= Solution
For every <matching in a graph> $M'$ and every <vertex cover> $C'$, the disjoint <edges> of $M'$ need distinct covering <vertices>. Therefore
$$
|M'|\le|C'|,\qquad\nu(G)\le\tau(G).
$$
Now 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,
$$
\tau(G)\le|C|=|M|\le\nu(G)\le\tau(G).
$$
Every inequality must be equality, proving <Kőnig's theorem for bipartite matching>:
$$
\boxed{\nu(G)=\tau(G).}
$$
Back to article page
