= Solution
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$:
$$
\boxed{C=\{\text{one chosen endpoint of each edge of }M\}.}
$$
The argument also covers an edgeless <graph>: take both sets empty.
Back to article page
