4.3. The Menger Theorem and its consequences
A nontrivial graph is connected if between every two distinct vertices of G there exists at least one path. This fact can be generalized in many ways, most of which involve, either directly or indirectly, a theorem due to Menger.
We recall that two u-v paths are independent if they have only the vertices u and v in common.
Theorem 4.5. (Menger's theorem, 1927): Let u
and v be distinct non-adjacent vertices of a graph G. Then the
minimum number of vertices separating u from v is equal to the
maximum number of independent paths.
Figure 4.2. Example to illustrate the Menger theorem
Proof. We will denote by the statement that the minimum number of
vertices that separate u and v is k.
The result is true if u and v lie in different components of G or if u and v lie in different blocks of G. So, we may assume that the graphs under consideration are connected and that u and v lie in the same block.
If is true, then the
maximum number of internally disjoint
paths in G
is at most k.
Thus, if then the result is true.
Suppose that the theorem is false. Then there exists a
smallest positive integer such that
is true in some graph G but the maximum
number of internally disjoint
paths is less than t.
Among all such graphs G of smallest order, let H be one of minimum size.
We now establish three properties of the graph H.
Lemma 4.6. For every two adjacent vertices and
of H, where neither
nor
is u or v,
there exists a set of U of
vertices of H such that
, separates u and v.
Proof. First, we will
show that if then
is false for
. To prove this, we claim that
is true for
.
If not then there exists a set W of vertices that
separates u and v in , where
. Then
W separates u and v in both
and
. So
separates u
and v in H, which is impossible.
Thus, as claimed, is true in
. So, there exists a set U
which separates u and v in
, where
. Then
, separates u and v in H.
Lemma
4.7. For each vertex in H, not both uw and vw
are edges of H.
Proof. Suppose that it
is not true. Then is true for
. Then, however,
contains
internally disjoint
paths. So, H
contains t internally disjoint
paths, which is a contradict-ion.
Lemma 4.8. If is a set of vertices which separates u
and v in H, then either
for all
or
for all
.
Proof. Suppose that the statement is false.
Define as the subgraph induced by the edges on all
paths in H that contain only one vertex of W.
Define
similarly.
We will show that . Suppose that the above statement is
not true. Then both
and
have order at least
.
Define to consist of
, a new vertex
together with all edges
. Similarly,
we define
to consist of
, a new vertex
together with all edges
.
Observe that and
have smaller order than H. So,
is true in
and
is true in
. Therefore, there exist t
internally disjoint
paths in and t internally disjoint
paths in. These 2t paths produce t internally disjoint
paths in H.
This contradicts the condition that H is among those of graphs for which the number of internally disjoint paths is less then t.
Now, we can return to prove the statement of the Menger's theorem:
Let P be a path in H of length
. By Lemma
4.6.
. Thus we may write
where .
By Lemma 4.7., there exists a set U of vertices such that both
and
separate u and v.
Since v is not adjacent to , therefore every vertex of
is adjacent to u. (Lemma 4.8.)
Since u is not adjacent to
,
therefore every vertex of
is adjacent to v. (Lemma 4.8.)
Thus , which is a contradiction.
The Menger“s theorem has its "edge"-analogue:
Theorem 4.11. (Ford and Fulkerson, 1956): Let u
and v be distinct vertices of G. Then the minimal number of edges
separating u from v is equal to the maximal number of
edge-disjoint paths.
Corollary 4.12. A graph is k-edge-connected iff it has at least two vertices and any two
vertices can be joined by k edge-disjoint paths.