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.

Related Topics:
Mathematical - Graph theory - Connectivity - Finite undirected graph - Karl Menger - 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.

Related Topics:
Nonadjacent - Vertex cut - Vertex-independent path

~ ~ ~ ~ ~ ~ ~ ~ ~ ~