Proving Turán's Theorem by Symmetrization

From Clique-Free Graphs to Multipartite Graphs

Turán’s theorem asks how many edges a graph on \(n\) vertices can have while avoiding a clique of a specified size. The extremal graph is a balanced complete multipartite graph, but a direct search through all graphs is impractical. Symmetrization gives a structural route: modify an extremal graph so that its vertices fall into independent classes, with every pair of classes completely joined. Balancing those classes then gives the edge bound.

All graphs in this tutorial are finite and simple. A clique is a set of pairwise adjacent vertices, and \(K_{r+1}\)-free means containing no clique on \(r+1\) vertices. For positive integer \(r\) and nonnegative integer \(n\), let \(t_r(n)\) denote the maximum number of edges in a \(K_{r+1}\)-free graph on \(n\) vertices. A graph attaining this maximum is called extremal. At least one extremal graph exists because there are finitely many graphs on a fixed \(n\)-vertex set.

If \(G\) is \(K_{r+1}\)-free, this operation preserves that property. Any new \(K_{r+1}\) would have to contain \(x\), since other adjacencies are unchanged. It could not contain \(y\), because \(x\) and \(y\) are nonadjacent. Replacing \(x\) in that clique by \(y\) would give a \(K_{r+1}\) in the original graph: every other vertex in the clique was a neighbor of the new \(x\), hence was already a neighbor of \(y\). This contradiction proves preservation.

The edge count changes in a particularly simple way. Write \(\deg_G(v)\) for the degree of \(v\) before symmetrization. Only edges incident with \(x\) change, so the new edge count is \(|E(G)|-\deg_G(x)+\deg_G(y)\). In particular, cloning a vertex of smaller degree to one of larger degree does not decrease the number of edges.

Why an Extremal Graph Can Be Made Multipartite

Preserving the forbidden-clique condition and not decreasing the edge count is not, by itself, enough to show that symmetrization finishes in a multipartite graph. We use a secondary quantity to prove the required structure. Among all \(K_{r+1}\)-free graphs with \(t_r(n)\) edges, choose one, \(G\), for which the sum of squared degrees is as large as possible. Such a choice exists because there are finitely many candidates.

Proof. Suppose instead that \(x,y\) are nonadjacent and \(N(x)\ne N(y)\). If their degrees differ, assume first that \(\deg(x)<\deg(y)\), interchanging their names if needed. Symmetrizing \(x\) to \(y\) preserves \(K_{r+1}\)-freeness and increases the edge count by \(\deg(y)-\deg(x)>0\). This contradicts the definition of \(t_r(n)\). Therefore every such pair has equal degree; write their common degree as \(d\).

Define \(A=N(x)\setminus N(y)\) and \(B=N(y)\setminus N(x)\). Since the neighborhoods differ, \(|A|+|B|>0\). For a vertex \(w\), write \(d_w=\deg_G(w)\), and define \(Q(G)=\sum_{w\in V(G)}\deg_G(w)^2\). When \(x\) is symmetrized to \(y\), the degrees of \(x\) and \(y\) remain \(d\). Each vertex of \(A\) loses one edge and each vertex of \(B\) gains one edge; all other degrees remain unchanged. Consequently the change in \(Q\) is $$ 2\left(\sum_{w\in B}d_w-\sum_{w\in A}d_w\right)+|A|+|B|. $$ If the operation is reversed, symmetrizing \(y\) to \(x\), the change is $$ 2\left(\sum_{w\in A}d_w-\sum_{w\in B}d_w\right)+|A|+|B|. $$ The sum of these two changes is \(2(|A|+|B|)>0\), so at least one direction strictly increases \(Q\). In either direction, the edge count stays the same because the two degrees are equal, and the graph remains \(K_{r+1}\)-free. This contradicts the choice of \(G\) as having maximum \(Q\) among extremal graphs. Hence nonadjacent vertices must have identical neighborhoods. \(\square\)

We now turn that neighborhood condition into a multipartite structure. Relate vertices when they are equal or when they are nonadjacent and have identical neighborhoods. This is an equivalence relation: the only nontrivial point is transitivity. If \(u\) and \(v\), and \(v\) and \(w\), are nonadjacent pairs with identical neighborhoods, then \(N(u)=N(v)=N(w)\). Since \(w\notin N(v)\), also \(w\notin N(u)\), so \(u,w\) are nonadjacent and belong to the same class. Each class is independent: adjacent vertices cannot have identical neighborhoods, because one would belong to its neighbor’s neighborhood but not its own.

Between distinct classes, every possible edge is present. If a vertex from one class were nonadjacent to a vertex from another, the lemma would give them identical neighborhoods, putting them in the same class. Thus \(G\) is complete multipartite: its vertices are partitioned into independent classes, with all edges between different classes. If there are \(k\) nonempty classes, choosing one vertex from each gives a \(k\)-clique. Since \(G\) is \(K_{r+1}\)-free, \(k\le r\).

Balancing the Parts

For a complete multipartite graph with part sizes \(a_1,\ldots,a_r\), allow empty parts if there are fewer than \(r\) nonempty classes. Its edge count is \(\sum_{i<j}a_i a_j\): each edge joins a unique pair of parts. Since \(\sum_i a_i=n\), this is also \((n^2-\sum_i a_i^2)/2\). Thus, for a fixed \(n\), more edges result from smaller sum of squared part sizes.

Proof. Suppose two parts have sizes \(a\) and \(b\), with \(a\ge b+2\). Move one vertex from the part of size \(a\) to the part of size \(b\). The total number of vertices in those two parts stays fixed, and edge counts involving any other part are unchanged. The number of edges between the two selected parts changes from \(ab\) to \((a-1)(b+1)\), a difference of \((a-1)(b+1)-ab=a-b-1>0\). Thus an unbalanced pair can be replaced by a pair with more edges. Repeating this operation must stop: the nonnegative integer \(\sum_i a_i^2\) strictly decreases at each move. When it stops, no two sizes differ by two or more, which is precisely the stated condition. \(\square\)

Write \(n=qr+s\), where \(q=\lfloor n/r\rfloor\) and \(0\le s<r\). The balanced sizes are \(q+1\) for \(s\) parts and \(q\) for the other \(r-s\) parts. This includes \(n<r\), when \(q=0\) and some parts are empty.

Turán’s Theorem

Proof. Choose an extremal \(K_{r+1}\)-free graph. By the lemma, it is complete multipartite with at most \(r\) nonempty parts. Pad its list of part sizes with zeros to obtain \(r\) sizes summing to \(n\). By the balancing proposition, its edge count is at most that of the balanced complete \(r\)-partite graph. Conversely, that balanced graph is \(K_{r+1}\)-free: a clique can contain at most one vertex from each of its \(r\) independent parts. It is therefore a valid construction attaining the bound. Its squared part sizes sum to \(s(q+1)^2+(r-s)q^2\); substituting this sum into the edge-count formula proves the displayed expression. When \(n=0\), all parts are empty and both the graph’s edge count and the formula are zero, so the statement also holds in that case. \(\square\)

Common Pitfall

A common error is to balance parts but forget that the number of edges is half of \(n^2-\sum_i a_i^2\). For the part sizes \(3,2,2\), an incorrect calculation might report \(49-(9+4+4)=32\) edges. That expression counts each cross-part edge twice: once from each endpoint’s part. The correction is \((49-17)/2=16\). The direct count \(3\cdot2+3\cdot2+2\cdot2=16\) confirms the factor of one-half.

The symmetrization argument is useful because it separates the extremal problem into two tasks: first obtain a structure without reducing the edge count, then optimize the part sizes. The secondary degree-square quantity is essential to the structural step; edge count alone does not guarantee that an equal-edge symmetrization makes progress. The conclusion here supplies the extremal value and a construction attaining it.