# Proof for Menger's Theorem

Menger's Theorem is defined in Introduction to Graph Theory as follows:

Menger's Theorem. Let $u$ and $v$ be nonadjacent vertices in a graph $G$. The minimum number of vertices in a $u-v$ separating set equals the maximum number of internally disjoint $u-v$ paths in $G$.

Following the statement of the theorem, the authors give a really long inductive and by-cases proof. I find this puzzling because it seems to me that the following simple proof by contradiction would suffice:

Proof. Let $k$ be the cardinality of a minimum $u-v$ separating set, and let $l$ be the number of internally disjoint $u-v$ paths. Assume, to the contrary, that $l \neq k$. Then either $l < k$ or $l > k$. If $l < k$, then removing $l$ vertices from $G$, one vertex from each of the $l$ $u-v$ paths, disconnects $u$ and $v$ which is a contradiction. Similarly, if $l > k$, removing $k$ vertices will not disconnect $u$ and $v$; rather we would need to remove $l$ vertices to disconnect $u$ and $v$ which is, again, a contradiction.

Is there something I am missing?

-
It's probably a good idea to replace your images with text. –  Qiaochu Yuan Aug 10 '11 at 21:20
@ Qiaochu Yuan: I spent an hour trying to figure out how do that nicely, any tips? –  Isaac Kleinman Aug 10 '11 at 21:26
There's not much to it. Enclose mathematical text in dollar signs. If you're having trouble with the less-than and greater-than signs, it's because they're being parsed as html; use \lt and \gt instead. –  Qiaochu Yuan Aug 10 '11 at 21:31

You mean $\ell$ is the maximum number of internally disjoint $uv$-paths in $G$. It is indeed fairly straightforward to see that $\ell \le k$, since removing less than $\ell$ vertices cannot disconnect all of $\ell$ disjoint paths.

It is not fairly straightforward to see that $\ell \ge k$. If $\ell < k$, then removing $\ell$ vertices from $G$ may disconnect a particular choice of a set of internally disjoint paths, but that doesn't imply that some other path can't exist from $u$ to $v$ which you haven't disconnected. "Internally disjoint" is a condition on a set of paths, not a condition on a path.

Menger's theorem is known to be equivalent in some sense to Hall's marriage theorem and several other theorems that, while not difficult to prove, do require a nontrivial idea. They aren't trivially true. The proof I know uses max-flow min-cut (which can also be used to prove Hall's theorem).

-
Why the emphasis on maximum number of internally disjoint uv-paths? The proof of the theorem seems to indicate that there are exactly k internally disjoint uv-paths. –  Isaac Kleinman Aug 14 '11 at 17:54
@Isaac: I don't know what you mean by that. As I said, "internally disjoint" is a condition on a set of paths, not a condition on a path. There is a set of sets of internally disjoint paths, some of which contain more paths than others, and you are interested in the ones with the maximum number of paths. –  Qiaochu Yuan Aug 14 '11 at 18:42

The problem comes from the idea of removing one vertex from each path - it is unclear that it actually disconnects u and v. The choice of vertices is very important. Just because the paths themselves are disjoint does not mean that there aren't edges between the vertices of one path and the vertices of another path - vertex selection matters.

If this isn't clear, I recommend drawing a set of paths that $do$ connect to each other and take vertices out at random. As soon as you see a case where one vertex taken from each does not disconnect u and v, you'll see the problem.

(I don't know any method of drawing a graph here, but I recommend a sort of H graph for a simple idea - where the top feet of the H connect to v, and bottom feet connect to u - there are clearly 2 disjoint paths, but if we remove a vertex near the top of the left bar and the bottom of the right bar, u and v are still connected, but not across either of the initial disjoint paths).

-

First of all, $l$ should be the maximum number of internally disjoint $u-v$ paths.

The second part is correct: $l \leq k$ since given $l$ internally disjoint paths, you need to remove at least one (different) vertex from each. The other direction is not so clear: suppose you remove one vertex from each path, how do you know that $u$ and $v$ are now disconnected?

Consider the following example: $$- \lozenge$$ Here $u$ is to the left, $v$ is to the right, there is a vertex $a$ in the middle and two other vertices $1,2$. The edges are thus $$(u,a) (a,1) (a,2) (1,v) (2,v).$$ Removing $1$ or $2$ does not disconnect $u$ from $v$. We have to remove $a$. So it can happen that you remove one vertex from each of the $l$ paths without disconnecting $u$ from $v$.

-
Why the emphasis on maximum number of internally disjoint uv-paths? The proof of the theorem seems to indicate that there are exactly k internally disjoint uv-paths. –  Isaac Kleinman Aug 14 '11 at 17:54
Take a star on $1+n$ vertices, label one of the outer vertices as $u$, and connect the rest of the outer vertices to a new vertex $v$ (the example above has $n=2$). Now there are $n-1$ paths $u-v$, but no two are internally disjoint. The point is that disjointness is a property that a particular subset of the paths satisfies, it isn't a property of all paths at once - indeed, only rarely all the $u-v$ paths are internally disjoint. –  Yuval Filmus Aug 14 '11 at 22:08