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 the subgraph.

It is not too hard to show that Menger's theorem holds for infinite graphs. The following statement 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. 

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. 

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Graph connectivity Network theory Theorems in discrete mathematics Combinatorics stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем решить контрольную работу Graded vector space Universe (documentary) Look at other dictionaries: Menger — may refer to: People Andreas Menger (born 1972), former German football player Anton Menger (1841–1906), Austrian economist and author; brother of Carl Menger Carl Menger (1840–1921), Austrian economist and author founder of the Austrian School… …   Wikipedia Menger sponge — An illustration of M4, the fourth iteration of the construction process. In mathematics, the Menger sponge is a fractal curve. It is a universal curve, in that it has topological dimension one, and any other curve (more precisely: any compact… …   Wikipedia Menger curvature — In mathematics, the Menger curvature of a triple of points in n dimensional Euclidean space Rn is the reciprocal of the radius of the circle that passes through the three points. It is named after the Austrian American mathematician Karl Menger.… …   Wikipedia Max-flow min-cut theorem — In optimization theory, the max flow min cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the minimum capacity which when removed in a specific way from the network causes the… …   Wikipedia Karl Menger — This article is about the mathematician (who also contributed to economics), not about his father, the economist Carl Menger. Karl Menger (Vienna, Austria, January 13 1902 – Highland Park, Illinois, U.S., October 5 1985) was a mathematician of… …   Wikipedia Marriage theorem — In mathematics, the marriage theorem (1935), usually credited to mathematician Philip Hall, is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of subsets.Formally, let S = { S …   Wikipedia Hall's marriage theorem — In mathematics, Hall s marriage theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets. It was proved by Philip Hall (1935). Contents 1 Definitions and …   Wikipedia Satz von Menger — Ein Schnitt bezeichnet in der Graphentheorie eine Menge von Kanten eines Graphen G = (V,E), die zwischen zwei Mengen von Knoten bzw. zwischen einer Menge und der Restmenge liegt. Eine besondere Bedeutung kommt Schnitten im Zusammenhang mit… …   Deutsch Wikipedia Connectivity (graph theory) — In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… …   Wikipedia List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”