Science Fair Project Encyclopedia
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 by Karl Menger in 1927 and later generalized by the max flow min cut theorem.
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.
Last updated: 05-12-2005 15:23:58
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details