Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem?
Konig's Theorem is as follows:
For a bipartite graph $G$, the maximum size of a matching equals the minimum size of a vertex cover.
Menger's Theorem is as follows:
Let $G$ be a graph and let $u$ and $v$ be two nonadjacent vertices. Then the minimum vertex cut for $u$ and $v$ (the minimum number of vertices whose removal disconnects $u$ and $v$) is equal to the maximum number of pairwise vertex-disjoint $u,v$-paths.
Thank you!
Best Answer
Let $G$ be a bipartite graph with bipartition $(A,B)$. The idea is to apply Menger's Theorem to a new graph $G^\prime$ obtained from $G$ by adding two vertices $u$ and $v$, and joining $u$ to all vertices in $A$, and $v$ to all vertices in $B$.
Now you just need to check that a matching in $G$ corresponds to a set of internally-disjoint $(u,v)$-paths in $G^\prime$, and a vertex cover in $G$ corresponds to a $(u,v)$-cut in $G^\prime$.