1
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.