= Solution
<Turan theorem> states that among all $N$-vertex graphs containing no $K_{r+1}$, the maximum number of <edges> is attained by the <Turán 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\geq b+2$, moving one vertex from the larger part to the smaller changes the number of cross-edges by
$$
a-b-1>0.
$$
\b[Thus 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.]
Back to article page
