Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 3 / 17G / i / Solution

Turan theorem states that among all $N$-vertex graphs containing no $K_{r+1}$, the maximum number of edges is attained by the Turan graph $T_r(N)$, the complete multipartite graph whose $r$ part sizes differ by at most one.

Here is the Zykov symmetrization proof. Start with an extremal $K_{r+1}$-free graph. If nonadjacent vertices $u,v$ have different neighbourhoods, replace the lower-degree vertex by a clone of the higher-degree one: delete all its incident edges and join it to precisely the neighbours of the other vertex. This does not decrease the number of edges and cannot create a $K_{r+1}$, because a clique using the clone corresponds to one using the original vertex. Repeating the operation, with the standard tie-breaking that merges equal-neighbourhood classes, produces a complete multipartite extremal graph. It has at most $r$ nonempty parts, since choosing one vertex from each part gives a clique.

If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller changes the number of cross-edges byThus an extremal partition has exactly $r$ parts whose sizes differ by at most one. This is $T_r(N)$ and proves the theorem. For $r=2$ it is Mantel theorem: a triangle-free graph on $N$ vertices has at most $\lfloor N^2/4\rfloor$ edges.