2
$\begingroup$

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?

Thanks

  • 0
    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.2011-08-26

1 Answers 1

3

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.