Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 2 / 17F (Graph Theory)

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.

For $r\ge 3$, join a clique on $r-2$ vertices to an independent set on $n-r+2$ vertices. The resulting complete $(r-1)$-partite graph hasIts largest clique has size $r-1$. Every missing edge joins two vertices of the independent set; adding it produces a $K_r$ with the original $(r-2)$-clique. It is therefore maximal $K_r$-free. For $n>r$ its part sizes are unbalanced, so its edge count is strictly less than that of $T_{r-1}(n)$.

For $r=3$ the construction is a star with $n-1$ edges. Every maximal triangle-free graph on $n>3$ vertices is connected: an edge between distinct components would create no triangle. A connected graph has at least $n-1$ edges, so the minimum is $n-1$, attained by the star. Literally the requested construction is impossible for $r=2$, since $T_1(n)$ has zero edges. The nontrivial assertion thus requires the customary $r\ge 3$ hypothesis.