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.


1 Answer 1


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}$$


$$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.

  • $\begingroup$ 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? $\endgroup$ Dec 20, 2012 at 15:17
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 20, 2012 at 16:45
  • $\begingroup$ 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? $\endgroup$ Dec 20, 2012 at 20:34
  • 1
    $\begingroup$ @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$. $\endgroup$ Dec 21, 2012 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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