In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger in 1927, it characterizes the connectivity of a graph. It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.
The edge-connectivity version of Menger's theorem is as follows:
The implication for the graph G is the following version:
The vertex-connectivity statement of Menger's theorem is as follows:
A consequence for the entire graph G is this version:
All these statements in both edge and vertex versions remain true in directed graphs (when considering directed paths).
Most direct proofs consider a more general statement to allow proving it by induction. It is also convenient to use definitions that include some degenerate cases. The following proof for undirected graphs works without change for directed graphs or multi-graphs, provided we take path to mean directed path.
For sets of vertices A,B â G (not necessarily disjoint), an AB-path is a path in G with a starting vertex in A, a final vertex in B, and no internal vertices either in A or in B. We allow a path with a single vertex in A â© B and zero edges. An AB-separator of size k is a set S of k vertices (which may intersect A and B) such that GâÂÂS contains no AB-path. An AB-connector of size k is a union of k vertex-disjoint AB-paths.
In other words, if no kâÂÂ1 vertices disconnect A from B, then there exist k disjoint paths from A to B. This variant implies the above vertex-connectivity statement: for x,y â G in the previous section, apply the current theorem to GâÂÂ{x,y} with A = N(x), B = N(y), the neighboring vertices of x,y. Then a set of vertices disconnecting x and y is the same thing as an AB-separator, and removing the end vertices in a set of independent xy-paths gives an AB-connector.
Proof of the Theorem: Induction on the number of edges in G. For G with no edges, the minimum AB-separator is A â© B, which is itself an AB-connector consisting of single-vertex paths.
For G having an edge e, we may assume by induction that the Theorem holds for GâÂÂe. If GâÂÂe has a minimal AB-separator of size k, then there is an AB-connector of size k in GâÂÂe, and hence in G.
Otherwise, let S be a AB-separator of GâÂÂe of size less than k, so that every AB-path in G contains a vertex of S or the edge e. The size of S must be k-1, since if it was less, S together with either endpoint of e would be a better AB-separator of G. In GâÂÂS there is an AB-path through e, since S alone is too small to be an AB-separator of G. Let v<sub>1</sub> be the earlier and v<sub>2</sub> be the later vertex of e on such a path. Then v<sub>1</sub> is reachable from A but not from B in GâÂÂSâÂÂe, while v<sub>2</sub> is reachable from B but not from A.
Now, let S<sub>1</sub> = S ⪠{v<sub>1</sub>}, and consider a minimum AS<sub>1</sub>-separator T in GâÂÂe. Since v<sub>2</sub> is not reachable from A in GâÂÂS<sub>1</sub>, T is also an AS<sub>1</sub>-separator in G. Then T is also an AB-separator in G (because every AB-path intersects S<sub>1</sub>). Hence it has size at least k. By induction, GâÂÂe contains an AS<sub>1</sub>-connector C<sub>1</sub> of size k. Because of its size, the endpoints of the paths in it must be exactly S<sub>1</sub>.
Similarly, letting S<sub>2</sub> = S ⪠{v<sub>2</sub>}, a minimum S<sub>2</sub>B-separator has size k, and there is an S<sub>2</sub>B-connector C<sub>2</sub> of size k, with paths whose starting points are exactly S<sub>2</sub>.
Furthermore, since S<sub>1</sub> disconnects G, every path in C<sub>1</sub> is internally disjoint from every path in C<sub>2</sub>, and we can define an AB-connector of size k in G by concatenating paths (kâÂÂ1 paths through S and one path going through e=v<sub>1</sub>v<sub>2</sub>). Q.E.D.
The directed edge version of the theorem easily implies the other versions. To infer the directed graph vertex version, it suffices to split each vertex v into two vertices v<sub>1</sub>, v<sub>2</sub>, with all ingoing edges going to v<sub>1</sub>, all outgoing edges going from v<sub>2</sub>, and an additional edge from v<sub>1</sub> to v<sub>2</sub>. The directed versions of the theorem immediately imply undirected versions: it suffices to replace each edge of an undirected graph with a pair of directed edges (a digon).
The directed edge version in turn follows from its weighted variant, the max-flow min-cut theorem. Its proofs are often correctness proofs for max flow algorithms. It is also a special case of the still more general (strong) duality theorem for linear programs.
A formulation that for finite digraphs is equivalent to the above formulation is:
In this version the theorem follows in fairly easily from KÃ Ânig's theorem: in a bipartite graph, the minimal size of a cover is equal to the maximal size of a matching.
This is done as follows: replace every vertex v in the original digraph D by two vertices v' , v<nowiki></nowiki>, and every edge uv by the edge u'v<nowiki></nowiki>; additionally, include the edges v'v<nowiki></nowiki> for every vertex v that is neither in A nor B. This results in a bipartite graph, whose one side consists of the vertices v' , and the other of the vertices v<nowiki></nowiki>.
Applying KÃ Ânig's theorem we obtain a matching M and a cover C of the same size. In particular, exactly one endpoint of each edge of M is in C. Add to C all vertices a<nowiki></nowiki>, for a in A, and all vertices b' , for b in B. Let P be the set of all AB-paths composed of edges uv in D such that u'v<nowiki></nowiki> belongs to M. Let Q in the original graph consist of all vertices v such that both v' and v<nowiki></nowiki> belong to C. It is straightforward to check that Q is an AB-separating set, that every path in the family P contains precisely one vertex from Q, and every vertex in Q lies on a path from P, as desired.
Menger's theorem holds for infinite graphs, and in that context it applies to the minimum cut between any two elements that are either vertices or ends of the graph . The following result of Ron Aharoni and Eli Berger was originally a conjecture proposed by Paul Erdà Âs, and before being proved was known as the Erdà ÂsâÂÂMenger conjecture. It is equivalent to Menger's theorem when the graph is finite.