Menger's theorem
In the mathematical discipline of graph theory and related areas, Menger's theorem is a characterization of the connectivity in finite undirected graphs in terms of the minimum number of disjoint paths that can be found between any pair of vertices. It was proved for edge-connectivity and vertex-connectivity by Karl Menger in 1927. The edge-connectivity version of Menger's theorem was later generalized by the max-flow min-cut theorem.
Edge connectivity
The edge-connectivity version of Menger's theorem is as follows:
- Let G be a finite undirected graph and x and y two distinct vertices. Then the theorem states that the size of the minimum edge cut for x and y (the minimum number of edges whose removal disconnects x and y) is equal to the maximum number of pairwise edge-independent paths from x to y.
- Extended to subgraphs: a maximal subgraph disconnected by no less than a k-edge cut is identical to a maximal subgraph with a minimum number k of edge-independent paths between any x, y pairs of nodes in the subgraph.
Vertex connectivity
The vertex-connectivity statement of Menger's theorem is as follows:
- Let G be a finite undirected graph and x and y two nonadjacent vertices. Then the theorem states that the size of the minimum vertex cut for x and y (the minimum number of vertices whose removal disconnects x and y) is equal to the maximum number of pairwise vertex-independent paths from x to y.
- Extended to subgraphs: a maximal subgraph disconnected by no less than a k-vertex cut is identical to a maximal subgraph with a minimum number k of vertex-independent paths between any x, y pairs of nodes in the subgraph.
Reductions to the directed and to the bipartite cases
The directed graphs vertex version of the theorem implies the undirected version by a familiar device of replacing every edge by a digon (doubly directed edge). The validity of the theorem for the resulting digraph easily implies its validity for the original, undirected, graph.
A formulation that for finite digraphs is equivalent to the above formulation is:
Let A and B be sets of vertices in a finite digraph G. Then there exists a family P of disjoint A-B-paths and an A-B separating set that consists of exactly one vertex from each path in P.
In this version the theorem follows in a straightforward manner from König's duality 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'', and every edge uv by the edge u'v''. This results in a bipartite graph, whose one side consists of the vertices v', and the other of the vertices v''.
Applying König's theorem we obtain a cover C and a matching M of the same size. Add to C all vertices a'', a in A, and all vertices b', b in B. Let now the Q in the original graph consist of all vertices v such that both v' and v'' belong to C, and let P be the set of all A-B paths in D such that x'y'' belongs to M for every xy in the edge set of the path. It is straightforward to check that Q is an A-B separating set, and that every path in the family P contains precisely one vertex from Q, as desired.[1]
Infinite graphs
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 (Halin 1974). 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.
- Let A and B be sets of vertices in a (possibly infinite) digraph G. Then there exists a family P of disjoint A-B-paths and a separating set which consists of exactly one vertex from each path in P.
See also
References
- Menger, Karl (1927). "Zur allgemeinen Kurventheorie". Fund. Math. 10: 96–115.
- Aharoni, Ron & Berger, Eli (2009). "Menger's Theorem for infinite graphs". Inventiones Mathematicae. 176: 1–62. doi:10.1007/s00222-008-0157-3.
- Halin, R. (1974), "A note on Menger's theorem for infinite locally finite graphs", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 40: 111–114, doi:10.1007/BF02993589, MR 0335355.