Turán's theorem

Statement

Let $n \ge r \ge 1$ be integers, and let $G$ be a simple graph with $n$ vertices that has no clique with $r + 1$ vertices. Then $G$ has at most as many edges as the Turán graph $T(n, r)$. In particular, $G$ has at most $\left(1 - \frac{1}{r}\right) \frac{n^2}{2}$ edges.

Remarks

The bound is sharp, because $T(n, r)$ has no clique with $r + 1$ vertices. The case $r = 2$ is Mantel's theorem on graphs without triangles. The theorem is a central result of extremal graph theory.

History

Pál Turán described the theorem and the Turán graphs in 1941.

Explanations

L1 human

How many edges can a graph have if no $r + 1$ of its vertices are all joined to each other? The answer is the Turán graph: split the vertices into $r$ balanced teams and join all pairs across teams.