# 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') = A*_{1}∪A_{2},
where *A*_{1} is the set
of those arcs of *D* whose flow is zero, and
*A*_{2} 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 *A*_{1}
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 *A*_{1} 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 *A*_{1} which are incident with
*u*.

The sum of the capacities on the arcs of
*A*_{1} 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') = A*_{1}∪A_{2},
where *A*_{1} is the set
of those arcs *e∈A(D)* for which *f(e)<c(e)*, and
*A*_{2} 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∈A*_{1}∩A(P)}
∪
{f(e):e∈A_{2}∩A(P)}.
Let *g* be the flow with support *A(P)*,
*g(e)=α* for
*e∈A*_{1}∩A(P), and
*g(e)=−α* for
*e∈A*_{2}∩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 *b*^{−}b^{+}.
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 *b*^{−}b^{+}, 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 *b*^{−}b^{+}.
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 *b*^{−}b^{+}, 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^{−},e^{−}a,e^{−}b}.

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 *a*_{1}, *a*_{2}, ...,
*a*_{k}, and permutation matrices
*P*_{1}, *P*_{2}, ...,
*P*_{k}, such that
*A = a*_{1}P_{1} +
a_{2}P_{2}
... + a_{k}P_{k}.

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.