Exercise 2146Combinatorics › Graph theoryM1Added 3 Nov 2026
Turán's theorem
#Turán#extremal#clique
Statement
State Turán's theorem on the maximum number of edges in a -free graph.
Hint
The Turán graph (complete -partite with balanced parts) maximizes edges among -free graphs.
Show solutionHide solution
Solution
Theorem. The maximum number of edges in a graph on vertices containing no is achieved by the Turán graph :
Exact. More precisely, when .
Conclusion. Turán's theorem is the starting point of extremal graph theory.