Menger's theorem

In the mathematical discipline of graph theory and related areas, Menger's theorem is a basic result about connectivity in finite undirected graphs. 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.

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.

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 t is equivalent to Menger's theorem for finite graphs and is a deep recent result of Ron Aharoni and Eli Berger for infinite graphs (originally a conjecture proposed by Paul Erdős):

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.

References

• Menger, Karl (1927). "Zur allgemeinen Kurventheorie". Fund. Math. 10: 96–115. 
• Aharoni, Ron and Berger, Eli (2009). "Menger's Theorem for infinite graphs". Inventiones Mathematicae 176: 1–62. doi:10.1007/s00222-008-0157-3. http://www.springerlink.com/content/267k231365284lr6/?p=ddccdd0319b24e53958e286488757ca7&pi=0. 
• 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, MR0335355 .

External links

• "A Proof of Menger's Theorem". http://www.math.unm.edu/~loring/links/graph_s05/Menger.pdf. 
• "Menger's Theorems and Max-Flow-Min-Cut". http://www.math.fau.edu/locke/Menger.htm. 
• "Network flow". http://gepard.bioinformatik.uni-saarland.de/teaching/ws-2008-09/bioinformatik-3/lectures/V12-NetworkFlow.pdf.  and
• "Max-Flow-Min-Cut". http://gepard.bioinformatik.uni-saarland.de/teaching/ws-2008-09/bioinformatik-3/lectures/V13-MaxFlowMinCut.pdf.