Deduce the undirected edge version of Menger's theorem from the directed version

179 Views Asked by At

Menger's theorem says, in directed graph $G$, $k$ is the maximum number of arc-disjoint $st$-dipaths if and only if the size of the minimum $st$-cut is $k$. Use this version of Menger's theorem to prove the undirected version.

Sufficiency is clear. For necessity, Wikipedia says "replace each vertex with a digon", but what if the $k$ arc-disjoint dipaths use the two arcs that form a digon (i.e. $(u,v)$ and $(v,u)$). Why won't this happen? Or, how do we find $k$ edge-disjoint $st$-paths if this happens?

1

There are 1 best solutions below

1
On BEST ANSWER

Out of all possible collections of $k$ pairwise arc-disjoint $s-t$ paths, take one with the minimum total length. We will show that this one never uses both arcs $(u,v)$ and $(v,u)$ for any $u,v$.

Suppose that one path consists of an $s-u$ segment $P$, the arc $(u,v)$, and then a $v-t$ segment $Q$; meanwhile, another path consists of an $s-v$ segment $P'$, the arc $(v,u)$, and then a $u-t$ segment $Q'$. Reassemble these into two shorter $s-t$ paths: one made up of $P$ and $Q'$, the other made up of $P'$ and $Q$. This contradicts minimality.

(Fine print: the two shorter $s-t$ paths might actually be $s-t$ walks, because $P$ and $Q'$ might share some vertices, for instance. But from the edges of any $s-t$ walk, we can put together an $s-t$ path, which would be even shorter than what we had.)