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.

I'm reading the proof of Menger's therom, in Diestel's book, "Graph Theory, 3rd edition". Here's the statement:

Theorem 3.3.1.

Let $G = (V, E)$ be a graph and $A, B \subseteq V $. Then the minimum number of vertices separating $A$ from $B$ in $G$ is equal to the maximum number of disjoint $A–B$ paths in $G$.

As far as I can see, there's a trivial case that is contradictory with this statement. Consider two sets that contains only one node $A=\{a\}$, $B=\{b\}$. Since A itself is a separation of $A, B$, then the the minimum number of vertices separating $A$ from $B$ is no more than 1, but clearly, there might be many disjoint $A-B$ path existing.

I guess it's just a technical problem which can be fixed by slightly changing the definition of "separate" or "$A-B$ path". But what are these fixes?


Another thing about Menger's theorem that I don't get is this corollary in the same book:

Corollary 3.3.5. Let a and b be two distinct vertices of G.

(i) If $ab \notin E$, then the minimum number of vertices $\neq a, b$ separating a from b in G is equal to the maximum number of independent a–b paths in G.

This is said to be a direct result of Theorem 3.3.1, but why do we need the condition that "a" and "b" are NOT adjacent?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

I think you need to define what "disjoint $A−B$ path" means. The author here probably not only requires internal vertices of a path to be disjoint, but also the two endpoints. Then in your example, you only have one disjoint $A-B$ path, since $|A|=|B|=1$. In general, you don't need to remove all of $A$ or $B$ since there might be a bottle neck somewhere in the middle so you can remove much less vertices in order to disconnect $A$ and $B$.

Concerning your second question, the corollary talks about the internal vertex-disjoint $a-b$ paths (the author uses the term "independent path", I assume that this is what it means) and the removal of vertices other than $a$ and $b$. If $a$ and $b$ are adjacent, you can never disconnect them by removing other vertices.

share|improve this answer
    
You are right : "Two or more paths are independent if none of them contains an inner vertex of another." I should read the introduction part more carefully! –  ablmf Oct 23 '11 at 15:16
    
But then, how can you apply a theorem about number of disjoint path on number of independent path? –  ablmf Oct 23 '11 at 15:24
1  
@ablmf Take $A$ to be the neighborhood of $a$ and take $B$ to be the neighborhood of $b$. The set of vertices disconnecting the two also disconnects $a$ and $b$. –  sxu Oct 23 '11 at 15:40

Since I also found this issue rather confusing while learning about Menger's theorem, I'm collecting the relevant definitions in Diestel's book to clear things up. All references are to Chapter 1 of the free preview of the fourth edition.

A path is a non-empty graph $P=(V,E)$ of the form

$$V=\{x_0,x_1,\dotsc,x_k\}\quad\quad E=\{x_0x_1,x_1,x_2,\dotsc,x_{k-1}x_k\}\;,$$

where the $x_i$ are all distinct. The vertices $x_1,\dotsc,x_{k-1}$ are the inner vertices of $P$. (p. 6)

Two graphs are disjoint if they have no vertices or edges in common (p. 3). Thus two paths are are disjoint if they have no vertices or edges in common.

Two or more paths are independent if none of them contains an inner vertex of another (p. 7)

If $A,B\subseteq V$ and $X\subseteq V\cup E$ are such that every $A$–$B$ path in $G$ contains a vertex or an edge from $X$, then $X$ separates the sets $A$ and $B$ in $G$. (p. 11)

I believe carefully applying those definitions to the theorems you quoted will clear up the confusion.

share|improve this answer

Your Answer

 
discard

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.