Maths WorkshopMaths problems with full solutions
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 Kr+1K_{r+1}-free graph.

Hint

The Turán graph T(n,r)T(n,r) (complete rr-partite with balanced parts) maximizes edges among Kr+1K_{r+1}-free graphs.

Show solutionHide solution

Solution

Theorem. The maximum number of edges in a graph on nn vertices containing no Kr+1K_{r+1} is achieved by the Turán graph T(n,r)T(n,r):
e(T(n,r))=(1−1r)n22−(remainder).e(T(n,r))=\left(1-\frac1r\right)\frac{n^2}{2}-\text{(remainder)}.

Exact. More precisely, e=r−12rn2e=\frac{r-1}{2r}n^2 when r∣nr\mid n.

Conclusion. Turán's theorem is the starting point of extremal graph theory.