MENGER’S THEOREM

TERENCE TAO

1. Introduction

We now present a basic tool in network theory, namely Menger’s theorem for directed graphs.

Definition 1.1 (Directed graphs). A directed graph is a pair G = G(V, E) where V is a finite non-empty vertex set, and E ⊂ V × V is a set of ordered pairs of vertices; we denote a typical edge e ∈ E as e = (a → b) for some a, b ∈ V. If A, B are two disjoint subsets of V, we define a simple path γ from A to B in G to be any collection (a_{0} → a_{1}), (a_{1} → a_{2}), …, (a_{n−1} → a_{n}) of edges in G with n > 0 such that a_{0} ∈ A, a_{n} ∈ B, and the vertices a_{0}, …, a_{n} are disjoint; we refer to the set V (γ) := {a_{0}, …, a_{n}} as the vertex set of γ. We say that two simple paths γ, γ′ are vertex-disjoint if their vertex sets are disjoint, and edge-disjoint if their edge sets are disjoint; thus vertex-disjointness implies edge-disjointness but not vice versa.

Let F ⊂ E be any collection of edges in G. This set of edges defines an integervalued flux F (v) for every vertex v ∈ V, defined by

F (v) := |{(a → b) ∈ E : b = v}| − |{(a → b) ∈ E : a = v}|.

We say that v is a source for F if the flux F (v) is negative, and a sink if the flux is positive. Since every edge has one sink and one source, we see that the net flux ∑_{v∈V} F (v) of F is zero. We thus define the capacity cap(F) of the edge collection F by

cap(F) := ∑_{F (v)>0} F (v) = − ∑_{F (v)<0} F (v) = \frac{1}{2} ∑_{v∈V} |F (v)|.

We say that F is a flow from A to B if all the sources of F are in A and all the sinks are in B.

Clearly every simple path from A to B is a flow with capacity 1, while every simple closed path is a flow with capacity zero. Moreover, every union of edge-disjoint simple paths from A to B and simple closed paths is a flow with capacity equal to the number of paths from A to B. The converse is also true:

Lemma 1.2. Let G = (V, E) be a finite directed graph, and let A and B be disjoint subsets of V. Let F be a flow in G from A to B. Then we can decompose F = γ_{1} ∪ … ∪ γ_{n} ∪ l_{1} ∪ … l_{k}, where γ_{1}, …, γ_{n} are edge-disjoint simple paths from A to B, and l_{1}, …, l_{k} are simple closed paths which are edge-disjoint from each other and from γ_{1}, …, γ_{n}. Furthermore, we have cap(F) = n.

Proof We induct on the number of edges in F. If F has no edges the claim is trivially true. If F contains a cycle, then it contains a simple cycle, and we may remove this path from F and E and use induction. Now suppose that F contains no cycles. If e = (a → b) is an edge in F, then either b ∈ B, or there is an edge (b → c) which is also in F. Thus every edge e in F can be propagated forward until it stops somewhere in B (recall F has no cycles). Similarly each edge can be propagated backward until it stops somewhere in A. Thus every edge e is contained in a simple path in F from A to B. Again we may remove this path from F and E (decreasing the capacity by one) and again use induction.

Define the edge capacity e-cap_{G}(A → B) of a graph G from A to B to be the maximum value of cap(F), where F ranges over all flows from A to B; in other words, e-cap_{G}(A → B) is the largest number of edge-disjoint simple paths in G that can be given from A to B.

Define an edge cut C in G disconnecting A from B to be any set C ⊂ E of vertices such that e-cap_{G−E}(A → B) = 0; in other words, every simple path from A to B must pass through at least one element of E. Note that if E is a cut, then we must have |C| ≥ e-cap_{G}(A → B), since every member of a edge-disjoint family of paths requires a separate element of C to cut it. Menger’s theorem, which is a special case of the famous max-flow-min-cut theorem about the capacity of networks, asserts that this estimate is sharp, in that one can always find a cut C of cardinality |C| = e-cap_{G}(A → B):

Theorem 1.3 (Menger’s theorem, edge-disjoint version). Let G = (V, E) be a finite directed graph, let A, B be disjoint subsets of V, and let γ_{1}, …, γ_{n} be edge-disjoint paths in G from A to B, where n = e-cap_{G}(A → B) is the edge capacity of G from A to B. Then there exists a edge cut C = {c_{1}, …, c_{n}} ⊆ E in G disconnecting A from B such that c_{j} ∈ γ_{j} for all 1 ≤ j ≤ n.

Proof We use the Ford-Fulkerson algorithm. Let F := γ_{1} ∪ … ∪ γ_{n} be the flow induced by γ_{1}, …, γ_{n}. We then form the modified graph G′ := (V, E′), where E′ is formed by taking those edges in E, but reversing the orientation of the edges which also lie in F. In other words, we have E′ := (E\F) ∪ (−F), where −F := {(b → a) : (a → b) ∈ F } is the reversal of F.

We claim that ∩_{G′}(A → B) = 0. To see this, suppose for contradiction that there was a simple path γ in G′ from A to B. We may split γ = X ∪ −Y, where X := γ ∩ (E\F) and −Y := γ ∩ (−F). Then the set F′ := (F \Y) ∪ X can easily be seen to be a flow in G of capacity n+1 (this is the same flow as F ∪γ, but cancelling the edges Y ∪ −Y), but this contradicts the maximality of n = e − ∩_{G}(A → B). Thus there are no paths from A to B in G′.

Let X ⊂ V be the set of all vertices v ∈ V which can be reached from A via a path in G′. By what we have just discussed, X contains A but is disjoint from B. In particular, every path γ_{j} must contain an edge c_{j} = (a_{j} → b_{j}) whose initial point a_{j} lies in X but whose final point b_{j} lies outside of X. Indeed, this edge c_{j} is unique, since every vertex earlier than a_{j} in γ_{j} lies in A (one can reach those vertices from a_{j} via −γ_{j} ⊂ F′), and conversely every vertex later than b_{j} in γ_{j} cannot lie in X.

To finish the proof of the theorem, we need to show that C := {c_{1}, …, c_{n}} is an edge cut in G disconnecting A from B. Suppose for contradiction that there is a path γ in G from A to B which does not contain any edges from C. Since A lies in X and B is disjoint from X, there must be an edge (a → b) in γ such that a ∈ X and b ∉ X. But then (a → b) cannot lie in G′ (otherwise a ∈ X would imply b ∈ X), so (a → b) must lie in one of the paths γ_{j}. But by the preceding paragraph this is only possible when (a → b) = c_{j}, contradiction.

Although the edge-disjoint version of Menger’s theorem is the easiest to prove, for our purposes we will actually need the following vertex-disjoint version. Define the vertex capacity v-cap_{G}(A → B) of G from A to B to be the largest number of vertex-disjoint paths in G that one can subtend from A to B; this is clearly less than or equal to the edge capacity. Define a vertex cut in G disconnecting A from B to be a set C ⊂ V of vertices such that v-cap_{G−V} (A → B) = 0, i.e. every path from A to B must pass through at least one vertex in V. Once again, it is clear that we have |C| ≥ v-cap_{G}(A → B) for all vertex cuts C, and we have an analogue of Menger’s theorem that says that this is again sharp:

Theorem 1.4 (Menger’s theorem, vertex-disjoint version). Let G = (V, E) be a finite directed graph, let A, B be disjoint subsets of V, and let γ_{1}, …, γ_{n} be vertexdisjoint paths in G from A to B, where n = v-cap_{G}(A → B) is the vertex capacity of G from A to B. Then there exists a vertex cut C = {c_{1}, …, c_{n}} ⊆ V in G disconnecting A from B such that c_{j} ∈ V (γ_{j}) for all 1 ≤ j ≤ n.

Proof We shall lift this vertex-disjoint problem into an edge-disjoint problem by the following trick. We form another (disjoint) copy V′ of the vertex set V, with each vertex v ∈ V being associated with a vertex v′ ∈ V′, and form the graph G̃ = (Ṽ , Ẽ) with vertex set Ṽ := V ∪ V′ and edge set

Ẽ := {(a′ → b) : (a → b) ∈ E} ∪ {(a → a′) : a ∈ V };

in other words, we blow up every vertex in V to itself be an edge. Every simple path γ in G from A to B then lifts to a simple path γ̃ from A to B′, defined by

γ̃ := {(a′ → b) : (a → b) ∈ γ} ∪ {(a → a′) : a ∈ V (γ)},

and conversely every simple path γ̃ in G̃ from A to B′ arises from a simple path γ in G from A to B in this manner. Furthermore, two paths γ, γ′ in G are vertexdisjoint if and only if their corresponding lifts γ̃, γ̃′ are edge-disjoint. Thus the vertex capacity of G equals the edge capacity of G̃. We may then apply Theorem 1.3 to the edge-disjoint paths γ̃_{1}, …, γ̃_{n} in G̃ to create an edge cut C̃ = {c̃_{1}, …, c̃_{n}} in G̃ disconnecting A from B′. Each edge c̃_{j} lies in γ̃_{j}, and we in fact claim that it is of the form c̃_{j} = (c_{j} → c′_{j}) for some vertex c_{j} ∈ V (γ_{j}). For if this were not the case, the only other possibility is that c̃_{j} = (a′_{j} → b_{j}) for some a′_{j} ∈ V′, b_{j} ∈ V. But by construction of c̃_{j} we see that a′_{j} lies in the set X defined in the proof of Theorem 1.3, while b_{j} does not lie in X. But this is absurd as the only edge in the modified graph G̃′ (formed by starting with G̃ and reversing all the paths γ̃_{1}, …, γ̃_{n}) that ends in a′_{j} is the one that starts from b_{j}. Thus we have c̃_{j} = (c_{j} → c′_{j}) for all j. Since {c̃_{1}, …, c̃_{n}} is an edge cut of G̃, we thus see that {c_{1}, …, c_{n}} is a vertex cut of G.

One consequence of Menger’s theorem is

Theorem 1.5 (Hall’s marriage theorem). Let G(A, B, E) be a bipartite graph. Then G contains a perfect matching G′(A, B′, E′) if and only if one has |G(X)| ≥ |X| for all X ⊆ A, where G(X) is the set of all vertices in B which are adjacent to at least one vertex in X.

Proof Clearly, if an injection f : A → B with the above properties exists, then |G(X)| ≥ |f(X)| = |X| for all X. Conversely, suppose that no such function f exists. Let n := v-cap_{G}(A → B) be the vertex capacity of G. If n ≥ |A| then there exists |A| vertex-disjoint edges from A to B, which could be used to construct f, so we have n < |A|. Let (a_{1} → b_{1}), …, (a_{n} → b_{n}) be n vertex-disjoint edges in G. By Theorem 1.4, we can find a vertex cut C of n elements consisting of one vertex from each of the above edges; without loss of generality we may take C := {a_{1}, …, a_{k}, b_{k+1}, …, b_{n}}. But then if we set X := A\{a_{1}, …, a_{k}}, then we must have G(X) ⊆ {b_{k+1}, …, b_{n}}, otherwise we would violate the fact that C is a vertex cut. But |G(X)| = n − k < |A| − k = |X|.

2. An alternate proof

We now give an alternate proof of Menger’s theorem which does not reveal as much of the connection with network theory, but is somewhat simpler.

Theorem 2.1 (Menger’s theorem). Let G = G(V, E) be a graph, let A, B ⊆ V, and let k be the min cut from A to B. Then there exist k disjoint paths in G from A to B.

Proof We induct on |E|. When |E| = 0 all paths have length zero, k is at most |A ∩ B|, and the claim is trivial. Now assume that E contains at least one edge [a, b] and the claim has already been proven for all smaller values of E. We may assume that G has no loops since we could simply delete them without affecting the connectivity.

We divide into two cases. First suppose that there exists a disconnecting set C from A to B with the minimal cardinality k which contains the endpoints a, b of the specified edge. Observe that if D ⊆ V disconnects A from C or disconnects C from B, then it will also disconnect A from B. We conclude that the min cut from A to C or from C to B is at least k. Also, if we remove [a, b] from E, then this does not affect the previous conclusion since that edge cannot possibly improve the connectivity from A to C or from C to B. We can now apply the induction hypothesis and find k disjoint simple paths from A to C, and k disjoint simple paths from C to B. Since |C| = k, we conclude that each c ∈ C will be the terminus of exactly one of the paths from A to C, and the starting point for exactly one of the paths from C to B. In particular, none of these paths pass through C except at endpoints. Also note that none of the paths from A to C can intersect one of the paths from C to B (except at C), since otherwise one could find a path from A to B which avoids C entirely, contradicting the hypothesis that C disconnects A from B. Thus we may concatenate the k paths from A to C with the k paths from C to B to create k disjoint simple paths from A to B, as desired.

It remains to consider the case in which none of the disconnecting sets C from A to B of minimal cardinality k contain both of the endpoints a, b of [a, b]. In this case we form a new graph G/(a = b) by identifying the vertices a and b (and thus identifying [a, c] and [b, c] for any c ∈ V \{a, b}), and deleting the edge [a, b] (which would have become a loop). Clearly this graph has fewer edges than E, and contains the sets A/(a = b) and B/(a = b), formed by identifying a with b (if they lie inside A and B). Suppose that there existed a set C/(a = b) disconnecting from A/(a = b) to B/(a = b) of cardinality less than k. Then this would imply that there existed a set C disconnecting A from B which either had cardinality less than k, or had cardinality equal to k and contained both a and b. But both possibilities are ruled out by previous assumptions. Thus the min cut of A/(a = b) and B/(a = b) is at least k. By induction hypothesis this implies that there are k disjoint simple paths in G/(a = b) which connect A/(a = b) to B/(a = b). At most one of these paths can pass through the identified vertex (a = b), and that path will only pass through (a = b) once. Thus we can undo the identification a = b and generate k disjoint simple paths in G which connect A to B, as desired. Thus in either case we can close the induction, and we are done.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu