Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Menger's theorem is stated as:

Let $G$ be a connected graph, and $a,b$ distinct non-adjacent vertices of $G$. If all $a$-$b$ separators have size $\geq k $, then there exists a family of $k$ independent $a$-$b$ paths.

A remark then says that "note that you cannot prove Menger by choosing one point on each path in a maximimum-sized "family of independent $a$-$b$ paths"." I don't understand what this statement is saying, at all. Any explanation would be appreciated. Thanks

EDIT: I think I've answered my original question in the comment below, but I have another related question. My notes state that an equivalent form is "minimum size of an $a$-$b$ separator = maximum number of independent $a$-$b$ paths". I don't see how this is equivalent; if the minimum size of an $a$-$b$ separator is $k$, why can't there be $k+1$ independent paths?


share|improve this question
I think I understand now, actually. We might be tempted to say "suppose all $a$-$b$ separators have size $\geq k$. Find a maximum-sized family of independent paths, and choose a point from each of these paths. Then the set of these points is an $a$-$b$ separator, and so there must be at least $k$ paths in the family". But the part in italics isn't necessarily true. Take, for example, a hexagon with one diagonal and have $a$ and $b$ one vertex clockwise from the start of the diagonal at each end. –  TRY Aug 26 '11 at 11:42
add comment

1 Answer

The reason that the minimum size separator between 2 vertices is a limit on the number of independent paths follows from the fact that each path must contain at least one of the separators. Each $a-b$ path must contain at least one seperator, a set of paths is only independent if they share no common edges.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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