= 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\geq r-1$, using fewer parts cannot be extremal if a part can be split. Finally its number of edges is $\frac12(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.
Back to article page
