1
$\begingroup$

The following proof for Menger's Theorem is given in Introduction to Graph Theory as follows:

Menger's Theorem. Let $u$ and $v$ be nonadjacent vertices in a graph $G$. The minimum number of vertices in a $u-v$ separating set equals the maximum number of internally disjoint $u-v$ paths in $G$.

Proof. We proceed by induction on the size of the graph. Certainly, the result is true vacuously for all empty graphs. Assume that the result is true for all graphs of size less than $m$, where $m$ is a positive integer, and let $G$ be a graph of size $m$. Let $u$ and $v$ be two nonadjacent vertices of $G$. Suppose that there are $k$ vertices in a minimum $u-v$ separating set. Certainly, $G$ can contain no more than $k$ internally disjoint $u-v$ paths. We show, in fact, that $G$ contains $k$ internally disjoint $u-v$ paths. We consider three cases.

(I'm only including the proof for the case I'm stuck on.)

Case 1. There exists a minimum $u-v$ separating set $U$ in $G$ containing a vertex $x$ that is adjacent to $u$ and $v$.

Case 2. There exists a minimum $u-v$ separating set $W$ in $G$ containing a vertex in $W$ that is not adjacent to $u$ and a vertex in $W$ that is not adjacent to $v$. Let $W = {w_1, w_2, \ldots, w_k}$. Let $G_u$ be the subgraph of $G$ consisting of all $u-w_i$ paths in $G$, where $w_i \in W$ for each $1 \leq i \leq k$ and let $G'_u$ be the graph obtained from $G_u$ by adding a new vertex $v'$ and joining $v'$ to each vertex $w_i$ for $1 \leq i \leq k$. Let $G_v$ and $G'_v$ be defines similarly, where $G'_v$ is obtained from $G_v$ by adding the new vertex $u'$.

Since $W$ contains a vertex that is not adjacent to $u$ and a vertex that is not adjacent to $v$, the size of each of the graphs $G'_u$ and $G'_v$ is less than $m$. Since $W$ is a minimum $u-v'$ separating set in $G'_u$, it follows by the induction hypothesis that $G'_u$ contains $k$ internally disjoint $u-v'$ paths, each consisting of a $u-w_i$ path $P_i$ followed by the edge $w_iv'$. Similarly, there are $k$ internally disjoint $u'-v$ paths in $G'_v$, each consisting of a $w_i-v$ path $Q_i$ preceded by the edge $u'w_i$. Since $W$ is a $u-v$ separating set in $G$, the two graphs $G_u$ and $G_v$, have only the vertices of $W$ in common. Therefore, the $k$ paths obtained by following $P_i$ by $Q_i$ for each $1 \leq i \leq k$ are internally disjoint $u-v$ paths in $G$.

Case 3. For each minimum $u-v$ separating set $S$ in $G$, either every vertex of $S$ is adjacent to $u$ and not adjacent to $v$ or every vertex of $S$ is adjacent to $v$ and not adjacent to $u$.

The part I'm getting stuck on is the assumption that "$W$ is a minimum $u-v'$ separating set in $G'_u$" (and in $G'_v$). How can we make this assumption?

$\endgroup$
1

1 Answer 1

0
$\begingroup$

Imagine like this. ${G'}_u$ and ${G'}_v$ resp. are obtained by collapse the right (left resp.) part of $G$ wrt. $W$ into $v'$ and $u'$ resp. So if you can find smaller $W'$ to separate any of these two new graphs, you have found a smaller separating set of $G$ contradicting definition of $W$.

$\endgroup$
1
  • $\begingroup$ If we can go with this approach, why do we need such an elaborate proof for the theorem altogether; the entire theorem can be proven with this assumption. $\endgroup$ Aug 14, 2018 at 14:36

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.