Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
