Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2011 / A / 1 / b / ii

Let the bipartition be $L\cup R$. Form an auxiliary graph by adding a new vertex $s$ adjacent to every vertex of $L$ and a new vertex $t$ adjacent to every vertex of $R$. The vertices $s,t$ are nonadjacent, so Menger's theorem applies.

A matching of size $m$ gives $m$ internally disjoint graph paths $s\ell rt$, one for each matching edge $\ell r$. Conversely, every $s$-$t$ graph path must use an edge of the original bipartite graph. Choose one such edge from each member of an internally disjoint family. Their endpoints are all distinct, so the chosen edges form a matching. Thus the maximum number of those graph paths is the maximum matching size.

An $s$-$t$ separator contained in $L\cup R$ is exactly a vertex cover of the original graph. Indeed, an uncovered edge $\ell r$ would leave the graph path $s\ell rt$, while removing a vertex cover removes every edge between $L$ and $R$ and hence every $s$-$t$ graph path. The minimum separator size is therefore the minimum vertex cover size. Menger givesThis is Kőnig's theorem for bipartite matching. The auxiliary construction gives the required deduction from vertex-disjoint paths rather than assuming a matching theorem in advance.