= Solution
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 gives
$$
\boxed{\nu(G)=\tau(G)\quad\text{for bipartite }G.}
$$
This 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.
Back to article page
