Menger's Theorems and Max-Flow-Min-Cut


There are several versions of Menger's Theorem, all can be derived from the Max-Flow-Min-Cut Theorem.
Undirected, Vertex Version. Let G be an undirected graph, and let u and v be nonadjacent vertices in G. Then, the maximum number of pairwise-internally-disjoint (u,v)-paths in G equals the minimum number of vertices from V(G)-{u,v} whose deletion separates u and v.
Directed, Vertex Version. Let D be a directed graph, and let u and v be vertices in G, with no arc from u to v. Then, the maximum number of pairwise-internally-disjoint directed (u,v)-paths in D equals the minimum number of vertices from V(D)-{u,v} whose deletion destroys all directed paths from u to v.
Undirected, Edge Version. Let G be an undirected graph, and let u and v be vertices in G. Then, the maximum number of pairwise-edge-disjoint (u,v)-paths in G equals the minimum number of edges from E(G) whose deletion separates u and v.
Directed, Arc Version. Let D be a directed graph, and let u and v be vertices in D. Then, the maximum number of pairwise-arc-disjoint directed (u,v)-paths in D equals the minimum number of arcs in A(D) whose deletion destroys all directed paths from u to v.
Connectivity. Let G be a k-connected graph. Then, for any pair of vertices, u and v, there are at least k pairwise-internally-disjoint (u,v)-paths in D.

Obviously, if some set of vertices, Y, separates u and v (that is, u and v are in different components of G-Y), then G is at most |Y|-connected.

Similar statements can be made for edge-connectivity, and for directed versions.
Max-Flow-Min-Cut. Let D be a directed graph, and let u and v be vertices in D. The maximum weight (sum of the flow weights on arcs leaving the source) among all (u,v)-flows in D equals the minimum capacity (sum of the capacities in the set of arcs in the separating set) among all sets of arcs in A(D) whose deletion destroys all directed paths from u to v.

Furthermore, there is a low-order polynomial-time algorithm which will find a maximum (u,v)-flow and a minimum capacity (u,v)-cut (a set of arcs in A(D) whose deletion destroys all directed paths from u to v).

Proof. We sketch the proof for the case in which all capacities are +1. A {0,1}-flow is function from the set of arcs to the set {0,1), such that sum of the flow on arcs into any vertex is the same as the sum of the flow on arcs out of the vertex, except for the two special vertices: the source, u, and the sink, v. The 0-flow is the flow which is zero on every arc.
Starting with any {0,1}-flow f, for example the 0-flow, we make a new directed graph, D', with V(D')=V(D) and with A(D') = A1∪A2, where A1 is the set of those arcs of D whose flow is zero, and A2 is the set of reversals of those arcs of D whose flow is one.

Suppose that there is a directed (u,v)-path, P, in D'. Let F denote the symmetric difference of A1 and P. Clearly, F is the set of edges of a flow f', where f' is one on arcs of F and zero on arcs not in F. Furthermore, F contains more arcs which are incident with u than A1 does.

Suppose, instead, that there is no directed (u,v)-path in D'. Let S denote the set of vertices in D' to which there is a directed path from u in D'. Then, in D, the set of arcs, C, leaving S must have cardinality exactly the same as the cardinality of the sets of arcs from A1 which are incident with u.

The sum of the capacities on the arcs of A1 which are incident with u is usually called the weight of the flow. Obviously, no {0,1}-flow can have weight exceeding |C|.

It is obvious that the above procedure finds a maximum flow and minimum cut, since no more than |A(D)| augmentation steps can be performed.


The proof for the general case is not much more difficult. However, the way we present it does not immediately lead to a polynomial-time algorithm.

Proof. Let the capacity on arc e be c(e) for each e∈A(D). A flow is function from the set of arcs to the set of reals, such that sum of the flow on arcs into any vertex is the same as the sum of the flow on arcs out of the vertex, except for the two special vertices: the source, u, and the sink, v. An admissible flow is a flow f such that 0≤f(e)≤c(e) for each e∈A(D). The 0-flow is the flow which is zero on every arc.

Starting with any admissible flow f, for example the 0-flow, we make a new directed graph, D', with V(D')=V(D) and with A(D') = A1∪A2, where A1 is the set of those arcs e∈A(D) for which f(e)<c(e), and A2 is the set of reversals of those arcs e∈A(D) for which f(e)>0.

Suppose that there is a directed (u,v)-path, P, in D'. Let α denote the minimum value in {c(e)−f(e):e∈A1∩A(P)} ∪ {f(e):e∈A2∩A(P)}. Let g be the flow with support A(P), g(e)=α for e∈A1∩A(P), and g(e)=−α for e∈A2∩A(P). Note, g is not an admissible flow, but f+g is an admissible flow, with weight α+w(f).

Suppose, instead, that there is no directed (u,v)-path in D'. Let S denote the set of vertices in D' to which there is a directed path from u in D'. Then, in D, the set of arcs, C, leaving S must have capacity exactly the same as the weight of f. No admissible flow can have weight exceeding c(C).




There is an easy example with four vertices and five arcs such that one can perform a very large number of ieterations.

However, if the capacities are all integers, we can can an algorithm which is polynomial in |A(D)|+|V(D)|+log(M), where M is the maximum of the capacities. Note that this is a lower bound on the size of the input data.

The trick is to replace the capacities by half of their values, rounded down, and producing a maximum weight flow f'. Then start the algorithm for our original D with the flow f=2f'. At most |A(D)| iterations are needed to obtain a maximum weight flow.

If we do this recursively, we divide the capacities in half at most log(M) times.




Menger's theorems.

Undirected, Vertex Version. Let G be an undirected graph, and let u and v be nonadjacent vertices in G. Then, the maximum number of pairwise-internally-disjoint (u,v)-paths in G equals the minimum number of vertices from V(G)-{u,v} whose deletion separates u and v.

For each vertex b, other than u or v, replace b by the 2-vertex graph H(b) with vertex set {b+,b} and arc bb+. Replace u by u+ and v by v. Replace each edge e=ab, {a,b} disjoint from {u,v}, by the arcs a+b and b+a. Replace each edge e=ub by the arc u+b. Replace each edge e=av by the arc a+v.

Any {0,1}-flow f in the new graph, D', yields a set P of pairwise-internally-disjoint directed (u,v)-paths in G, with |P|=w(f). Any cut C, a set of arcs whose deletion destroys all (u+,v)-paths in D' yields a set C' of arcs in D' of type bb+, with |C'|≤|C|, and no (u+,v)-paths in D'. This, in turn, yields a set of vertices C" in G, with |C"|≤|C'|, and no (u,v)-paths in D−C". But, then, for a maximum cardinality set P' of pairwise-internally-disjoint (u,v)-paths in G satisfies |P'|≥|P|=w(f)=|C|≥|C'|≥|C"|≥|P'|.


Directed, Vertex Version. Let D be a directed graph, and let u and v be vertices in G, with no arc from u to v. Then, the maximum number of pairwise-internally-disjoint directed (u,v)-paths in D equals the minimum number of vertices from V(D)-{u,v} whose deletion destroys all directed paths from u to v.

For each vertex b, other than u or v, replace b by the 2-vertex graph H(b) with vertex set {b+,b} and arc bb+. Replace u by u+ and v by v. Replace each arc e=ab by the arc a+b.

Any {0,1}-flow f in the new graph, D', yields a set P of pairwise-internally-disjoint directed (u,v)-paths in D, with |P|=w(f). Any cut C, a set of arcs whose deletion destroys all (u+,v)-paths in D' yields a set C' of arcs in D' of type bb+, with |C'|≤|C|, and no (u+,v)-paths in D'. This, in turn, yields a set of vertices C" in D, with |C"|≤|C'|, and no (u,v)-paths in D−C". But, then, for a maximum cardinality set P' of pairwise-internally-disjoint directed (u,v)-paths in D satisfies |P'|≥|P|=w(f)=|C|≥|C'|≥|C"|≥|P'|.


Undirected, Edge Version. Let G be an undirected graph, and let u and v be vertices in G. Then, the maximum number of pairwise-edge-disjoint (u,v)-paths in G equals the minimum number of edges from E(G) whose deletion separates u and v.

For each arc e=ab∈A(D) replace e by the 4-vertex graph H(e) with vertex set {a,b,e+,e} and arc set {ae+,be+,e+e,ea,eb}.

For the new directed graph, any minimum capacity cut C yields a set C' of edges in the original graph, with |C'|≤|C|. For any {0,1}-flow f in the new graph, yields a set of (u,v-paths P in the original graph, with |P|=w(f). Hence, a maximum cardinality set of (u,v-paths P' in the original graph has |P'|≥|P|=w(f)=|C|≥|C'|≥|P'|.


Directed, Arc Version. Let D be a directed graph, and let u and v be vertices in D. Then, the maximum number of pairwise-arc-disjoint directed (u,v)-paths in D equals the minimum number of arcs in A(D) whose deletion destroys all directed paths from u to v.

Let's leave one for the reader.




Matchings. A matching M in a graph G is a set of edges such that no two edges in M are incident with a common vertex. If G is bipartite with bipartition (X,Y), we say that M saturates X if for every vertex v∈X, there is some edge e∈M such that e is incident with v.

A cover is a set C of vertices of G such that G-C has no edges.
For a vertex v, the set of neighbours of v is denoted N(v). For any set of vertices S, N(S)=∪{N(v):v∈S}.

Hall's Theorem. If G is bipartite with bipartition (X,Y), then G has a matching M which saturates X if and only if for every S⊆X, |N(S)|≥|S|.

Konig-Egervary Theorem. If G is bipartite with bipartition (X,Y), if M is a maximum cardinality matching of G, and if C is a minimum cardinality cover of G, then |M|=|C|.

Proof (Hall's Theorem). One direction of the proof is obvious: if G has a matching M which saturates X then for every S⊆X, |N(S)|≥|S|.

Construct a new graph, D', with V(D')=V(G)∪{s,t}, where s and t are new vertices. Let A(D') = {xy:x∈X,y∈Y,xy∈E(G)} ∪ {sx:x∈X} ∪ {yt:y∈Y}. Let each arc of D' have capacity one. A minimum cut C of arcs in D' yields a set C' of arcs in D'−{s,t} with no (s,t)-path in D'−C', and |C'|≤|C|. A maximum weight flow f, yields a set P of pairwise-arc-disjoint paths, with |P|, and P yields a matching M, with |M|=|P|. Conversely, any maximum cardinality matching M' in G, yields a flow of weight |M'| in D'. Hence, a maximum cardinality matching M in G corresponds to maximum weight flow f in D' and |M|=w(f).

Let f be a maximum weight flow in D', let M be its associated matching, and let K be a minimum capacity (i.e., cardinality) cut set of arcs in D' separating s and t. Then, K gives us a set K'={sx:sx∈K}∪{yt:yt∈K}∪{yt:xy∈K}. Note that |K'|≤|K| and D'−K' has no (s,t)-path. Hence, |K'|=|K|.

Let C={y:yt∈K'}∪{x:sx∈K'}. Note that |C|=|K'|=|K|=w(f)=|M|. Also, G-C has no edges, since any edge xy in G-C yields a path sxyz which can be used to augment the flow. (We have now proven the Konig-egervary theorem).

If |C|≠|X|, then |M|=|C|<|X| (as X is a cover) and M does not saturate X. Let T=C∩Y and S=X−C. Then, N(S)⊆T. Now, |N(S)| ≤ |T| = |Y∩C| = |C|−|X∩C| < |X|−|X∩C| = |X−C| = |S|. We have a set S⊆X with |N(S)|<|S|, completing th proof of Hall's Theorem.




Birkhoff's theorem. let A be a doubly-stochastic matrix. That is, all entries of A are non-negative, every row of A sums to one, and every column of A sums to one. Then, there is an integer k, constants a1, a2, ..., ak, and permutation matrices P1, P2, ..., Pk, such that A = a1P1 + a2P2 ... + akPk.

Proof. We slightly modify the definition of doubly-stochastic matrix. Let's call a matrix A doubly-stochastic if all entries of A are non-negative, and there is a non-negative constant β such that every row of A sums to β, and every column of A sums to β. The usual case is simply the case in which β=1.

We now prove the result by induction on the number of zeroes in the matrix, with each step increasig the number of zeroes. If every entry of A is zero, there is nothing to prove. We have β=k=0.

Suppose that there is a positive entry in A, and thus β>0. Construct a bipartite graph G, with bipartition (X,Y), where X is the set of rows of A and Y is the set of columns of A. For x∈X and y∈Y, place an edge in G if A[x,y]>0. For an edge xy, we associate the weight A[x,y].

Let S⊆X. Consider the set of edges F from S to N(S). The sum of the weights of edges in F is |S|β, if we take this sum as these edges meet S. On the other hand, this sum is at most |N(S)|β, if we take this sum as these edges meet S, since vertices in N(S) might have neightbours not in S. Hence, |S|β≤|N(S)|β. Since β>0, |S|≤|N(S)|. Hall's conditions are satisfied, and G has a perfect matching M (a matching saturating V(G)).

Let α denote the minimum weight of an edge in M, and let P be the permutation matrix corresponding to the edges in M. Then, M−αP is a doubly-stochastic matrix with row and column sum β−α, and with at least one more zero than A. The result follows by induction.

The non-negativity conditions do not seem to be necessary. If A has negative entries, chose γ such that B=A+γJ has nonnegative entries, where J is the matrix of all ones. Write B as a non-negative linear combination of permutation matrices, and write J as a sum of permutation matrices (in any one of the many different ways this can be done). Then, A=B−γJ is a linear combination of permutation matrices (with some of the coefficients negative).




Last modified December 31, 2019, by S.C. Locke. How to contact me.