Turán's Theorem

Max edges with no K_r+1: (1 - 1/r) · n^2/2, uniquely achieved by the balanced complete r-partite graph.

The idea

Theorem (Turán's theorem).

Among all graphs on $n$ vertices that contain no clique of size $r+1$, the largest possible number of edges is $\mathrm{ex}(n, K_{r+1}) = \left(1 - \frac{1}{r}\right)\frac{n^{2}}{2},$ and the unique graph achieving it is the balanced complete $r$-partite Turán graph $T(n, r)$: divide the vertices into $r$ parts of as nearly equal size as possible, and join every pair of vertices that lie in different parts.

The theorem measures the global cost of a local prohibition. Forbidding a clique of size $r+1$ constrains only $r+1$ vertices at a time, yet it caps the edge count of the entire graph, and the formula locates the cap exactly.

The extremal graph explains the formula. In a complete multipartite graph no edge lies inside a part, so any $r+1$ vertices include two from the same part with no edge between them, and cannot form a clique; hence $T(n, r)$ is $K_{r+1}$-free. Balancing the parts maximizes the edges: moving a vertex from a smaller part to a larger one destroys more edges than it creates.

Ways to work on it

• Walkthrough. The triangle-free case — check that a balanced complete bipartite graph achieves the extremal bound.
• Practice. Compute the maximum edge count that avoids a clique, using Turán's formula.
• Hardest. Predict the extremal density of a general forbidden subgraph from its chromatic number.

Not sure where to start? Take the ten-question placement test.