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.