Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 2 / 17F / i / Solution

The Turán graph $T_r(n)$ is the complete $r$-partite graph with part sizes differing by at most one. Turan theorem states that a graph on $n$ vertices containing no $K_r$ has at most $e(T_{r-1}(n))$ edges, with equality precisely for that balanced complete multipartite graph.

Here is a symmetrization proof, including equality. Choose a $K_r$-free graph with the maximum number of edges. Replacing a vertex $u$ by a nonadjacent twin of a nonadjacent vertex $v$ preserves $K_r$-freeness: a clique using the replacement would give the same clique using $v$. Thus nonadjacent vertices must have equal degrees, or cloning the higher-degree vertex increases the edge count. In fact their neighborhoods are identical. Otherwise choose $w$ adjacent to $u$ but not $v$. Cloning $u$ to $v$ preserves the total number of edges but lowers $w$'s degree by one, leaving $v$'s degree unchanged. The still nonadjacent pair $w,v$ now has unequal degrees, allowing an edge-increasing clone and contradicting maximality.

Nonadjacency is consequently an equivalence relation, and the extremal graph is complete multipartite. It has at most $r-1$ parts because choosing one vertex from each part forms a clique. For $n\ge r-1$, using fewer parts cannot be extremal if a part can be split. Finally its number of edges is $\frac{1}{2}(n^2-\sum n_i^2)$, maximized uniquely by balanced sizes: moving a vertex from a part at least two larger than another decreases the sum of squares. This proves the theorem and its equality characterization. The cases with fewer vertices than the forbidden clique are immediate.