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.

How does exactly the induction go in the proof number one? What is the induction hypothesis there and what is the induction step?

By the induction hypothesis, $G/e$ contains an $A–B$ separator $Y$ of fewer than $k$ vertices.

Whole theorem and proof is here, page 67.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

As it says at the beginning of the proof, the induction is on $\|G\|$, the number of edges of $G$. The induction hypothesis is that Menger’s theorem is true for all graphs with fewer edges than $G$.

The proof then proceeds by contradiction. Suppose that $k$ is the minimum number of vertices separating $A$ and $B$ in $G$, but, contrary to Menger’s theorem, $G$ does not have $k$ disjoint $A$-$B$ paths. We’re assuming at this point that $\|G\|\ge 1$, so $G$ has an edge $e=xy$. Let $v_e$ be the contraction vertex in $G/e$, and set

$$A'=\begin{cases} A,&\text{if }A\cap\{x,y\}=\varnothing\\ \big(A\setminus\{x,y\}\big)\cup\{v_e\},&\text{if }A\cap\{x,y\}\ne\varnothing \end{cases}$$

and

$$B\,'=\begin{cases} B,&\text{if }B\cap\{x,y\}=\varnothing\\ \big(B\setminus\{x,y\}\big)\cup\{v_e\},&\text{if }B\cap\{x,y\}\ne\varnothing\;. \end{cases}$$

An $A'$-$B\,'$ path in $G/e$ that does not contain $v_e$ is an $A$-$B$ path in $G$, and an $A'$-$B\,'$ path in $G/e$ that does contain $v_e$ induces an $A$-$B$ path in $G$ in an obvious way. Moreover, it’s clear that disjoint $A'$-$B\,'$ paths in $G/e$ correspond to disjoint $A$-$B$ paths in $G$, so $G/e$ must have fewer than $k$ disjoint $A'$-$B\,'$ paths. Since $\|G/e\|=\|G\|-1<\|G\|$, the conclusion of Menger’s theorem hold for $G/e$ by the induction hypothesis, so $G/e$ has an $A'$-$B\,'$ separator $Y$ with fewer than $k$ vertices. This is the first of two points in the induction step at which the induction hypothesis is used; the argument continues as follows.

If the contraction vertex $v_e$ were not in $Y$, then $Y$ would be an $A$-$B$ separator in $G$, so $v_e\in Y$. Let $X=\big(Y\setminus\{v_e\}\big)\cup\{x,y\}$; then $X$ is an $A$-$B$ separator in $G$. By hypothesis $|X|\ge k$; on the other hand, $|X|=|Y|+1$, and $|Y|<k$, so we must have $|X|=k$. We now have an $A$-$B$ separator with exactly $k$ vertices.

Now suppose that $S$ is an $A$-$X$ separator in $G-e$. Every $A$-$B$ path in $G$ must pass through $X$ and therefore through $S$, so $S$ is an $A$-$B$ separator in $G$; thus, $|S|\ge k$. $\|G-e\|=\|G\|-1<\|G\|$, so the conclusion of Menger’s theorem holds for $G-e$, which therefore has $k$ disjoint $A$-$X$ paths. This is the second point in the induction step at which the induction hypothesis is used. Similarly, $G-e$ has $k$ disjoint $X$-$B$ paths. If one of these $A$-$X$ paths met one of these $X$-$B$ paths outside of $X$, we could construct from them an $A$-$B$ path in $G$ that did not go through $X$, which is impossible, so the $A$-$X$ paths are disjoint from the $X$-$B$ paths outside of $X$. Being disjoint, the $A$-$X$ paths must terminate in distinct vertices of $X$. Similarly, each of the $X$-$B$ paths begins at a distinct vertex of $X$. Thus, each of the $k$ $A$-$X$ paths $\pi$ can be paired up with the $X$-$B$ path beginning at the terminal vertex of $\pi$ to make an $A$-$B$ path, and the $k$ $A$-$B$ paths formed in this way are disjoint. That completes the proof.

share|improve this answer
    
Thanks for answer! What if $x \in A$ and $y \in B$? Should it be mentioned as a spesial case, where Menger theorem still stands or does this proof include it? –  Ohto Nordberg Dec 20 '12 at 15:17
1  
@Ohto: You’re welcome! It’s not a problem: in that case $v_e$ belongs to both $A'$ and $B\,'$, but it’s still one of the vertices in $Y$, and the proof goes through unchanged. –  Brian M. Scott Dec 20 '12 at 16:45
    
Ok, I see :). Now I fail to see the contradiction. The structure of this proof keeps eluding me ... What things become contradictory and where does it take this proof? I also have hard time understanding, why the graph G-e is considered. Is it because contracting "$/$" eliminates vertices and deleting "$-$" eliminates edges? –  Ohto Nordberg Dec 20 '12 at 20:34
1  
@Ohto: There are a couple of sub-arguments that use proof by contradiction, but overall it’s not a proof by contradiction: it’s a proof by induction on the number of edges, and the induction step shows how the desired $A$-$B$ paths. It uses $G/e$ to show that $G$ has an $A$-$B$ separator $X$ with exactly $k$ vertices, and then it uses $G-e$ to show that there must be $k$ disjoint paths from $A$ to $X$ and $k$ from $X$ to $B$ that can be ‘sewn together’ to make $k$ disjoint paths from $A$ to $B$. –  Brian M. Scott Dec 21 '12 at 0:34
add comment

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.