Menger's theorem
Theorem in graph theory / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Menger's theorem?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger in 1927, it characterizes the connectivity of a graph. It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.