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 among all (u,v)-flows in D
equals the minimum capacity 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 union 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|.
Last modified July 3, 1996, by S.C. Locke.
How to contact me.