Menger's theorem
Teorema de Menger
- Date
- 1927 · confidence high
- Place
- Vienna, Austria
- Credited to
- Karl Menger
- Field
- Knowledge & symbols
What was discovered
A graph theory theorem stating that in a finite graph the minimum size of a cut set between two vertices equals the maximum number of disjoint paths between them, proved by Karl Menger in 1927 and later generalized by the max-flow min-cut theorem.
What it led to
- fundamental characterization of graph connectivity
- later generalization via the max-flow min-cut theorem
- applications in designing robust, fault-tolerant networks
- theoretical basis for connectivity algorithms in computer science