Turán's theorem
Teorema de Turán
- Date
- 1941 · confidence low
- Place
- Hungary
- Credited to
- Pál Turán
- Field
- Knowledge & symbols
What was discovered
Turán's theorem, in graph theory, bounds the maximum number of edges an undirected graph can have without containing a complete subgraph of a given size. It was proved by Hungarian mathematician Pál Turán in 1941, and is one of the founding results of extremal graph theory.
What it led to
- Founding of extremal graph theory
- Generalizations such as the Erdős–Stone theorem
- Applications in combinatorics and theoretical computer science