Uniqueness of the Turán Extremal Graph

Equality Must Determine the Whole Graph

Turán’s theorem gives the maximum number of edges in a graph that contains no \(K_{r+1}\). Its balanced complete \(r\)-partite graph attains that maximum. The equality question is stronger: if a graph attains the bound, must it have that same structure? Yes. We prove that every extremal graph is isomorphic to the balanced Turán graph, and examine how balancing and symmetrization fit into the argument.

All graphs are finite and simple. A graph is \(K_{r+1}\)-free if it contains no complete subgraph on \(r+1\) vertices. A complete \(r\)-partite graph has its vertices partitioned into at most \(r\) parts, with two vertices adjacent exactly when they lie in different parts. The balanced complete \(r\)-partite graph on \(n\) vertices, denoted \(T_r(n)\), has part sizes differing by at most one. Write \(t_r(n)=|E(T_r(n))|\).

We use the edge bound in Turán’s theorem, established in the earlier material on Turán’s theorem: every \(K_{r+1}\)-free graph on \(n\) vertices has at most \(t_r(n)\) edges. We also use that \(T_r(n)\) attains this bound. The proof below establishes the equality structure for every extremal graph; it does not assume that symmetrizing an arbitrary graph preserves its isomorphism type.

What Balancing Says About Equality

If a complete \(r\)-partite graph has part sizes \(a_1,\ldots,a_r\), allowing empty parts, then every pair of vertices in different parts is an edge. Thus its edge count is \(\sum_{i<j}a_i a_j\). Since \(\sum_i a_i=n\), expanding the square of this sum gives

Proof. Suppose two part sizes satisfy \(x\ge y+2\). Move one vertex from the part of size \(x\) to the part of size \(y\). The change in the sum of squared part sizes is

By the edge-count formula, this strictly increases the number of edges. Therefore a maximizing choice cannot have two part sizes differing by at least two. Conversely, if all part sizes differ by at most one, no pair differs by two or more, so no such transfer can increase the edge count. More directly, for fixed integer sum, a sum of squares is minimized exactly when the entries differ by at most one: if entries differ by at least two, the displayed transfer decreases it, and a minimizing list can have no such pair. The edge-count formula then proves the claimed characterization. \(\square\)

This balancing fact characterizes the best part sizes once a graph is known to be complete multipartite. It does not by itself show that every extremal \(K_{r+1}\)-free graph is complete multipartite. For that, we use induction.

Proof of Uniqueness by Induction

For \(n=0\), there is only the empty graph. For \(1\le n\le r\), the graph \(T_r(n)\) is complete and has \(\binom n2\) edges. No graph on \(n\) vertices can have more than \(\binom n2\) edges, and attaining that count requires every possible edge. Thus the theorem holds for these base cases.

Now fix \(r\ge1\), take \(n>r\), and assume the uniqueness assertion holds on \(n-1\) vertices. Let \(G\) be any \(K_{r+1}\)-free graph on \(n\) vertices with \(t_r(n)\) edges. We first find a vertex whose degree is exactly \(t_r(n)-t_r(n-1)\).

Write \(n=ar+b\), where \(a\) and \(b\) are integers, \(a\ge1\), and \(0\le b<r\). The balanced part sizes are \(a+1\) for \(b\) parts and \(a\) for \(r-b\) parts. The edge-count formula gives

Removing a vertex from a largest part of \(T_r(n)\) leaves \(T_r(n-1)\). That vertex has degree \(n-\lceil n/r\rceil\), because its only non-neighbors are the other vertices in its part. Consequently,

We also need the average degree of \(G\). By the handshake lemma it is \(2|E(G)|/n=2t_r(n)/n\). If \(b=0\), the formula above gives \(2t_r(n)/n=(r-1)a=n-\lceil n/r\rceil\). If \(b>0\), then \(\lceil n/r\rceil=a+1\), and direct subtraction gives

Here \(0<b<r\) and \(n>b\), so the final expression is strictly between \(0\) and \(1\). In either case, \(\lfloor 2t_r(n)/n\rfloor=n-\lceil n/r\rceil\). At least one vertex \(v\) has degree no greater than the average: otherwise every degree would exceed the average, contradicting that their sum is \(2|E(G)|\). Since degrees are integers, this gives \(\deg(v)\le n-\lceil n/r\rceil\).

On the other hand, \(G-v\) is still \(K_{r+1}\)-free. By Turán’s bound it has at most \(t_r(n-1)\) edges. Therefore

Both degree bounds must be equalities. In particular, \(G-v\) has exactly \(t_r(n-1)\) edges. By the induction hypothesis, \(G-v\) is isomorphic to \(T_r(n-1)\).

It remains to determine precisely which vertices of \(G-v\) are adjacent to \(v\). Identify \(G-v\) with \(T_r(n-1)\), and let \(S=N(v)\), the set of neighbors of \(v\). The set \(S\) contains no \(K_r\): if it did, those \(r\) vertices together with \(v\) would form a \(K_{r+1}\) in \(G\). In a complete \(r\)-partite graph, any set meeting every part contains a \(K_r\), by choosing one vertex from each part. Hence \(S\) must miss at least one entire part.

The number of vertices outside \(S\) is

The last quantity is the size of a smallest part of \(T_r(n-1)\). Since \(S\) misses an entire part, its complement contains that part. The complement has exactly the size of a smallest part, so it must equal that part: it cannot contain the part and any additional vertex, nor can the missed part be larger. Thus \(v\) is nonadjacent exactly to one smallest part and adjacent to every other vertex. Adding \(v\) to that part produces a balanced complete \(r\)-partite graph on \(n\) vertices. Therefore \(G\cong T_r(n)\), completing the induction. \(\square\)

Worked Examples

Why Symmetrization Alone Is Not a Uniqueness Proof

Zykov symmetrization replaces one of two nonadjacent vertices by a copy of the other’s neighborhood. It is a powerful way to increase or preserve the edge count while keeping a graph \(K_{r+1}\)-free. When used to find an extremal graph, one can select an extremal graph maximizing a potential such as the sum of squared degrees; equality conditions then help show that this selected graph has strong symmetry.

That conclusion concerns the selected maximizer of the potential. It does not automatically describe every extremal graph: the symmetrization steps may change the graph’s isomorphism type. The invalid inference is “one extremal graph can be transformed into \(T_r(n)\), therefore every extremal graph is \(T_r(n)\).” The induction proof avoids that inference. It starts with an arbitrary extremal graph, forces a vertex of the required degree, and then forces its entire neighborhood pattern in the smaller Turán graph.

The balancing calculation has a parallel limitation. It proves that balanced part sizes maximize the edge count among complete multipartite graphs. To conclude uniqueness among all \(K_{r+1}\)-free graphs, one must also establish that an arbitrary extremal graph has the required multipartite structure. The induction supplies that missing step.