Tutte theorem
Teorema de Tutte
- Date
- 1947 · confidence high
- Place
- Cambridge, England, United Kingdom
- Credited to
- W. T. Tutte
- Field
- Knowledge & symbols
What was discovered
A graph-theory theorem characterizing finite undirected graphs that admit a perfect matching, via a condition on the number of odd-size components when any subset of vertices is removed; a special case of the Tutte-Berge formula.
What it led to
- Foundational result in matching theory
- Basis for polynomial-time algorithms testing for perfect matchings
- Influenced combinatorial optimization and network flow theory