Turán's theorem, from edges to eigenvalues
Abstract
Turán's theorem is the founding result of extremal graph theory: among all graphs on \(n\) vertices with no clique on \(r+1\) vertices, the balanced complete multipartite graph has the most edges. We present the theorem through five classical proofs and follow one of them, the variational argument of Motzkin and Straus, upward into spectral graph theory, where Nikiforov's spectral strengthening returns and proves the original theorem in two lines. All mathematics herein is known; the contribution is the form of its presentation.
This document is interactive: every section, theorem, proof, and step can be folded, traced, and linked. Use the controls at the left edge of each block.
1. Introduction: the extremal question
How many edges can a graph on \(n\) vertices have before some local structure becomes unavoidable? Questions of this shape define extremal graph theory, and the first of them was answered by Mantel in 1907 [2].
Theorem 1.1: Mantel (1907)
LET \(G\) be a triangle-free graph on \(n\) vertices. Then \(G\) has at most \(\lfloor n^2/4 \rfloor\) edges, and the unique triangle-free graph attaining this bound is the balanced complete bipartite graph \(K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor}\).
Turán's theorem [3] answers the question for cliques of every size \(r\) (Mantel's theorem is the case \(r = 2\)), and identifies the unique extremal graph. From now on, we WRITE \(\edges{G}\) for the number of edges of a graph \(G\).
Theorem 1.2: Turán (1941)
LET \(G\) be a graph on \(n\) vertices containing no clique on \(r+1\) vertices. Then
(1.1)
and more precisely \(\edges{G} \le \edges{\turan{n}}\), where \(\turan{n}\) is the Turán graph: the complete \(r\)-partite graph on \(n\) vertices with part sizes as equal as possible ( defined below). Equality \(\edges{G} = \edges{\turan{n}}\) holds if and only if \(G = \turan{n}\).
Turán's theorem is a statement about edges. The thesis of this paper is that it is equally a statement about eigenvalues. That destination is worth seeing before the journey: the same extremal bound controls the spectral radius \(\specrad\), the largest eigenvalue of the adjacency matrix. In Widget 1.1 you can edit the graph and choose which clique \(K_{r+1}\) to forbid; \(\specrad\) sits at or below the ceiling exactly when the graph is \(K_{r+1}\)-free, with the Turán graph tight against it. The sections that follow establish these results, and beyond, in full formality.
2. The extremal object
Definition 2.1.
LET \(n, r \ge 1\) be integers. WRITE \(\turan{n}\) for the complete \(r\)-partite graph on \(n\) vertices whose part sizes differ by at most one. We call \(\turan{n}\) the Turán graph. Parts may be empty; in particular, for \(n \le r\) every part has at most one vertex and \(\turan{n} = K_n\).
A complete multipartite graph contains no clique larger than its number of parts, so \(\turan{n}\) is \(K_{r+1}\)-free. Among complete \(r\)-partite graphs it is the edge-maximizer, which is the content of the following lemma.
Lemma 2.2: Balanced parts maximize
Among all complete \(r\)-partite graphs on \(n\) vertices, the maximum number of edges is attained exactly when the part sizes differ by at most one.
Proof sketch.
If two parts have sizes differing by at least two, moving a single vertex from the larger part to the smaller one strictly increases the number of edges. Hence any edge-maximal configuration is balanced, and all balanced configurations have the same number of edges.
Proof.
LET \(G\) be a complete \(r\)-partite graph on \(n\) vertices with parts \(A_1, \ldots, A_r\).
⟨1⟩
It SUFFICES to prove that moving one vertex from a part \(A_1\) to a part \(A_2\) with \(|A_1| \ge |A_2| + 2\) strictly increases the number of edges.
Such a move shows no unbalanced graph is edge-maximal, so every maximizer is balanced; balanced graphs, being mutually isomorphic, all share the same edge count.
⟨2⟩
ASSUME \(|A_1| \ge |A_2| + 2\).
⟨3⟩
⊢ Moving one vertex from \(A_1\) to \(A_2\) changes the number of edges by \(|A_1| - |A_2| - 1\).
Only edges incident to the moved vertex change, since adjacency in a complete \(r\)-partite graph depends only on the parts of the endpoints.
⟨4.1⟩
The moved vertex's degree goes from \(n - |A_1|\) to \(n - |A_2| - 1\), a difference of \(|A_1| - |A_2| - 1\).
⟨4.2⟩
⟨4⟩
Knowing the balanced graph is extremal still leaves its edge count unstated. Two facts about \(\edges{\turan{n}}\) recur in the proofs below. The first bounds that count by the clean quantity in (1.1), so that the sharp bound \(\edges{G} \le \edges{\turan{n}}\), which three of the proofs establish, carries the headline inequality with it.
Lemma 2.3: Turán graph edge bound
⊢ The Turán graph's edge count satisfies
(2.1)
with equality if and only if \(r\) divides \(n\).
Proof.
WRITE \(n_1, \ldots, n_r\) for the part sizes of \(\turan{n}\), so that \(n_1 + \cdots + n_r = n\). ⊢ Then
(2.2)
\(\turan{n}\) omits exactly the pairs lying in a common part, so \(\edges{\turan{n}} = \binom{n}{2} - \sum_i \binom{n_i}{2}\); expanding the binomials and using \(\sum_i n_i = n\) gives (2.2).
⟨1⟩
The second peels one vertex from each part, relating \(\edges{\turan{n}}\) to \(\edges{\turan{n-r}}\); it is the recurrence behind the inductive proof.
Lemma 2.4: Turán graph recursion
LET \(n > r\), then ⊢ the Turán graph's edge count satisfies
(2.3)
Proof.
WRITE \(\turan{n}\) as \(\turan{n-r}\) with one new vertex added to each of its \(r\) parts, some possibly empty when \(n < 2r\).
Adding one vertex to every part keeps the parts balanced, so on \(n\) vertices the result is \(\turan{n}\) by Definition 2.1.
⟨1⟩
⊢ The \(r\) new vertices contribute \(\binom{r}{2}\) edges.
They lie in distinct parts, so every pair among them is an edge.
⟨2⟩
⊢ The \(n - r\) old vertices contribute \((r-1)(n-r)\) new edges.
Each old vertex is joined to the one new vertex in each of the other \(r-1\) parts.
⟨3⟩
3. Five proofs
We give five proofs of Theorem 1.2, reaching it through different machinery, induction, symmetrization, degree comparison, continuous optimization, and averaging, yet each is in the end an answer to the same question: why no \(K_{r+1}\)-free graph can beat the balanced complete \(r\)-partite graph. That extremal graph and the \(K_{r+1}\)-free hypothesis are the only fixtures every proof shares. Everything else, the objects each one builds and the quantities it tracks, differs from lens to lens.
Three of the proofs are structural. Turán's induction and Zykov's symmetrization push an arbitrary extremal graph toward the Turán graph by local moves, the first by splitting off a clique and recursing, the second by making non-adjacent vertices into twins, each checking that no edge is lost on the way. Erdős's degree majorization trades surgery for a comparison of degree sequences, dominating \(G\) by a complete multipartite graph and reading off the bound. These three establish the exact bound \(\edges{G} \le \edges{\turan{n}}\), and symmetrization also pins down uniqueness; they are the lenses that travel furthest, the same reductions reappearing in stability results and, through the chromatic number, in the Erdős-Stone-Simonovits theorem, which fixes the extremal number of an arbitrary forbidden subgraph.
The last two proofs are analytic. Motzkin and Straus recast the discrete maximum as the maximum of a quadratic form over the probability simplex, trading combinatorics for convex optimization, while the probabilistic proof extracts the same bound from the expectation of a single random vertex ordering; both yield the clean form (1.1). The continuous lens is also the bridge to what follows: the quadratic form Motzkin and Straus maximize over the simplex is, over the unit sphere instead, the one whose maximum is the largest eigenvalue of the adjacency matrix. That is the thread the final section pulls.
Shared ideas are cross-referenced where they occur.
Each proof below is fully structured, in a hierarchical style proposed in [1]. As you read one, the sidebar tracks its live hypotheses and current goal, and lets you step through its dependency graph.
3.1. Turán's induction
Proof sketch.
Induct on \(n\) with \(r\) fixed. An edge-maximal \(K_{r+1}\)-free graph \(G\) contains a copy \(A\) of \(K_r\). The edges of \(G\) split into edges inside \(A\), edges from \(A\) to the rest, and edges inside the rest. The three contributions are at most \(\binom{r}{2}\), at most \((r-1)(n-r)\), and at most \(\edges{\turan{n-r}}\) by induction, which sum to exactly \(\edges{\turan{n}}\).
Proof of Theorem 1.2.
ASSUME \(n \le r\).
⟨1.1⟩
⊢ \(\turan{n} = K_n\).
For \(n \le r\) every part of \(\turan{n}\) holds at most one vertex by Definition 2.1, so all \(n\) vertices lie in distinct parts and are pairwise adjacent.
⟨1.2⟩
⊢ \(\edges{\turan{n}} = \binom{n}{2}\).
⟨1.3⟩
Every \(K_{r+1}\)-free graph \(G\) on \(n\) vertices has \(\edges{G} \le \binom{n}{2} = \edges{\turan{n}}\).
⟨1.5⟩
⟨1⟩
LET \(n > r\), ASSUME the bound for all \(K_{r+1}\)-free graphs on fewer than \(n\) vertices, and ASSUME \(G\) is edge-maximal, meaning that adding any edge creates a \(K_{r+1}\).
⟨2⟩
⊢ \(G\) contains a clique on \(r\) vertices.
PICK non-adjacent vertices \(u, v \in G\).
This is possible because \(G\) is not complete, since otherwise it would contain \(K_{r+1}\), violating the assumption in Theorem 1.2.
⟨3.1⟩
PICK a clique \(S\) on \(r+1\) vertices of \(G + uv\).
⟨3.2⟩
⊢ \(S\) contains both \(u\) and \(v\).
Otherwise \(S\) would already be a clique of \(G\), contradicting that \(G\) is \(K_{r+1}\)-free.
⟨3.3⟩
The set \(S \setminus \{v\}\) is a clique on \(r\) vertices.
⟨3.4⟩
⟨3⟩
LET \(A\) be a clique on \(r\) vertices and WRITE \(B = V(G) \setminus A\).
⟨4⟩
LET \(e(A,B)\) be the number of edges with one endpoint in each set and WRITE \(\edges{G} = e(A) + e(A, B) + e(B)\). ⊢ We immediately have \(e(A) = \binom{r}{2}\).
⟨5⟩
⊢ \(e(A, B) \le (r-1)(n-r)\).
Each of the \(|B| = n - r\) vertices of \(B\) sends at most \(r-1\) edges to \(A\). Otherwise, if one vertex \(w \in B\) had \(r\) edges to \(A\), then \(A \cup {w}\) would be a \(r+1\) clique, violating the hypotheses.
⟨6⟩
⊢ \(e(B) \le \edges{\turan{n-r}}\).
⟨7⟩
This argument establishes the bound only; carrying uniqueness through the induction would require a strengthened inductive hypothesis, and we obtain it instead from the symmetrization proof.
3.2. Zykov symmetrization
Proof sketch.
Take \(G\) edge-maximal among \(K_{r+1}\)-free graphs on \(n\) vertices. Replacing a vertex \(v\) by a twin of a non-neighbor \(u\) preserves \(K_{r+1}\)-freeness and changes the edge count by \(\deg u - \deg v\) [4]. Maximality then forces non-adjacency to be an equivalence relation, so \(G\) is complete multipartite with at most \(r\) parts, and Lemma 2.2 finishes the proof.
Proof of Theorem 1.2.
LET \(G\) be a graph with the maximum number of edges among all \(K_{r+1}\)-free graphs on \(n\) vertices.
⟨1⟩
It SUFFICES to show \(\edges{G} \le \edges{\turan{n}}\) for this \(G\).
⟨2⟩
WRITE \(G_{v \to u}\) for the graph obtained by deleting \(v\) and adding a new vertex \(u'\) adjacent to exactly the neighbors of \(u\). ⊢ If \(v\) and \(u\) are not neighbors, then \(\edges{G_{v \to u}} = \edges{G} - \deg v + \deg u\).
Deleting \(v\) removes \(\deg v\) edges; the twin \(u'\) contributes \(\deg u\) new ones. Since \(u \not\sim v\), deleting \(v\) does not change \(\deg u\).
⟨3⟩
PICK two non-adjacent vertices \(u, v\). ⊢ \(G_{v \to u}\) is \(K_{r+1}\)-free.
⊢ A clique of \(G_{v \to u}\) contains at most one of \(u\) and \(u'\).
⟨4.1⟩
⊢ Replacing \(u'\) by \(u\) in a clique of \(G_{v \to u}\) yields a clique of \(G\) of the same size.
Because \(u\) and \(u'\) have the same neighbors.
⟨4.2⟩
QED
⟨4.3⟩
⟨4⟩
⊢ Any two non-adjacent vertices of \(G\) have equal degree.
⟨5⟩
⊢ Non-adjacency is an equivalence relation on \(V(G)\).
LET \(u, v, w\) be vertices of \(G\). ASSUME toward a contradiction that \(u \not\sim v\), \(v \not\sim w\), but \(u \sim w\).
⟨6.1⟩
LET \(G' = G_{u \to v}\) and \(G'' = G'_{w \to v}\). It SUFFICES to prove \(G''\) is \(K_{r+1}\)-free with \(\edges{G} + 1\) edges.
⟨6.3⟩
⊢ \(G''\) is \(K_{r+1}\)-free.
⟨6.4⟩
⊢ \(\edges{G'} = \edges{G}\).
⟨6.5⟩
⊢ \(\edges{G''} = \edges{G} + 1\).
Deleting \(u\) drops \(\deg w\) to \(d - 1\) (as \(u \sim w\)), so Step ⟨3⟩ gives \(\edges{G''} = \edges{G'} - (d - 1) + d = \edges{G} + 1\).
⟨6.6⟩
QED
Such a triple is impossible, since \(G''\) would be a \(K_{r+1}\)-free graph with more edges than \(G\), against Step ⟨1⟩. So non-adjacency is transitive; being trivially reflexive and symmetric too, it is an equivalence relation.
⟨6.7⟩
⟨6⟩
⊢ \(G\) is complete multipartite with at most \(r\) parts.
Vertices in the same class are non-adjacent and vertices in different classes are adjacent.
⟨7.1⟩
Choosing one vertex from each of the \(s\) classes of Step ⟨7.1⟩ yields a \(K_s\), so \(s \le r\) since \(G\) is \(K_{r+1}\)-free.
⟨7.2⟩
⟨7⟩
⊢ For \(n > r\), \(G\) has exactly \(r\) parts.
PICK a part \(P\) with at least two vertices.
Since \(n > r > s\), there are more vertices than parts, so some part holds at least two of them.
⟨8.2⟩
WRITE \(G'\) for the complete multipartite graph obtained by splitting \(P\) into two nonempty parts \(P_1\) and \(P_2\).
It SUFFICES to show \(G'\) is \(K_{r+1}\)-free with \(\edges{G'} > \edges{G}\).
⟨8.3⟩
⊢ \(G'\) is \(K_{r+1}\)-free.
⟨8.4⟩
⊢ \(\edges{G'} > \edges{G}\).
Splitting \(P\) adds every edge between \(P_1\) and \(P_2\), both nonempty, and removes none.
⟨8.5⟩
⟨8⟩
⊢ \(\edges{G} \le \edges{\turan{n}}\), with equality iff \(G = \turan{n}\).
⟨9⟩
3.3. Erdős degree majorization
Proof sketch.
For every \(K_{r+1}\)-free graph \(G\) there is a complete multipartite graph \(H\) with at most \(r\) parts on the same vertex set with \(\deg_H(v) \ge \deg_G(v)\) for every vertex \(v\) [5]. The construction is by induction on \(r\), recursing on the neighborhood of a maximum-degree vertex. Summing degrees gives \(\edges{G} \le \edges{H}\), and complete multipartite graphs have at most \(\edges{\turan{n}}\) edges by Lemma 2.2.
Proof of Theorem 1.2.
It SUFFICES to find, for every \(K_{r+1}\)-free graph \(G\), a complete multipartite graph \(H\) with at most \(r\) parts, on the same vertex set, such that \(\deg_H(v) \ge \deg_G(v)\) for every vertex \(v\).
Summing the inequality over all vertices gives \(\edges{G} \le \edges{H}\). Splitting parts if necessary, \(H\) is a subgraph of a complete multipartite graph with exactly \(r\) parts (some of them possibly empty) on the same vertices, so \(\edges{H} \le \edges{\turan{n}}\) by Lemma 2.2. Hence \(\edges{G} \le \edges{\turan{n}}\), and equation (1.1) follows by Lemma 2.3.
⟨1⟩
We will proceed by induction on \(r\). First, the base case: ⊢ Such an \(H\) exists when \(V(G)\) is empty or \(r = 1\).
If \(V(G)\) is empty there is nothing to prove. If \(r = 1\) then \(G\) is \(K_2\)-free, hence has no edges, so \(H = G\), a single part.
⟨2⟩
LET \(r > 1\), and ASSUME as induction hypothesis that every \(K_r\)-free graph \(G'\) admits a complete multipartite graph on \(V(G')\) with at most \(r - 1\) parts whose degrees dominate those of \(G'\).
⟨3⟩
PICK a vertex \(w\) of \(G\) with maximum degree \(\Delta\) and WRITE \(N = N(w)\) for its neighborhood in \(G\). ⊢ \(G[N]\) is \(K_r\)-free.
A clique on \(r\) vertices inside \(N\) together with \(w\) would be a \(K_{r+1}\) in \(G\).
⟨4⟩
By the induction hypothesis applied to \(G[N]\), LET \(H'\) be a complete multipartite graph on \(N\) with at most \(r-1\) parts and \(\deg_{H'}(v) \ge \deg_{G[N]}(v)\) for every \(v \in N\).
⟨5⟩
WRITE \(S = V(G) \setminus N\), and WRITE \(H\) for the graph on \(V(G)\) whose edges are those of \(H'\) together with all pairs between \(S\) and \(N\). Then \(H\) is complete multipartite with at most \(r\) parts.
The parts of \(H\) are the parts of \(H'\) plus the new part \(S\).
⟨6⟩
⊢ \(\deg_H(v) \ge \deg_G(v)\) for every vertex \(v\), completing the induction.
⊢ For \(v \in S\), \(\deg_H(v) = |N| = \Delta \ge \deg_G(v)\).
⟨7.1⟩
⊢ For \(v \in N\), \(\deg_H(v) \ge \deg_G(v)\).
In \(H\), \(\deg_H(v) = \deg_{H'}(v) + |S| \ge \deg_{G[N]}(v) + |S|\) by Step ⟨5⟩, and this is at least \(\deg_G(v)\) since every neighbor of \(v\) in \(G\) lies in \(N\) or in \(S\).
⟨7.2⟩
⟨7⟩
3.4. Motzkin and Straus
This proof is central to our exposition: it converts the combinatorial statement into a continuous optimization, and the spectral results of the next section build on it. From now on, we LET \(\clq\) be the clique number of \(G\), the number of vertices in a largest clique of \(G\).
Theorem 3.1: Motzkin-Straus (1965)
LET \(\Delta_n = \{x \in \mathbb{R}^n : x_i \ge 0, \sum_i x_i = 1\}\) be the standard simplex on the \(n\) vertices of \(G\); we think of the \(i\)-th coordinate of \(\mathbb{R}^n\) as placing a weight \(x_i\) on vertex \(i\). Then
(3.1)
Proof sketch.
Establish that the left-hand side is greater than or equal the right-hand side, and, separately, also less than or equal to it. For the lower bound, place uniform weight \(1/\clq\) on the vertices of a maximum clique. For the upper bound, take a maximizer with smallest support. If its support contained a non-adjacent pair, weight could be shifted from one to the other without decreasing the objective, shrinking the support. Hence the support is a clique, and on a clique of size \(k\) the objective is at most \(1 - 1/k\) [6].
Proof of Theorem 1.2.
WRITE \(f(x) = 2 \sum_{\{i,j\} \in E} x_i x_j\). ⊢ The maximum of \(f\) over \(\Delta_n\) exists.
\(f\) is continuous and \(\Delta_n\) is compact.
⟨1⟩
⊢ \(\max_{x \in \Delta_n} f(x) \ge 1 - 1/\clq\).
PICK a clique \(K\) on \(\clq\) vertices and WRITE \(x_i = 1/\clq\) for \(i \in K\) and \(x_i = 0\) otherwise. All \(\binom{\clq}{2}\) pairs inside \(K\) are edges, so \(f(x) = 2 \binom{\clq}{2} / \clq^2 = 1 - 1/\clq\).
⟨2⟩
⊢ \(\max_{x \in \Delta_n} f(x) \le 1 - 1/\clq\).
⊢ Some maximizer of \(f\) has a clique as its support.
PICK a maximizer \(x^*\) SUCH THAT its support \(P = \{i : x^*_i > 0\}\) has the fewest elements among all maximizers.
Maximizers exist by Step ⟨1⟩, and support sizes are positive integers, so a maximizer of minimum support exists.
⟨3.1.1⟩
ASSUME toward a contradiction that some \(i, j \in P\) are distinct and non-adjacent.
⟨3.1.2⟩
WRITE \(s_k = 2 \sum_{l \sim k} x^*_l\) for twice the total weight adjacent to vertex \(k\). ⊢ Shifting an amount \(t\) of weight from \(i\) to \(j\) changes \(f\) by exactly \(t(s_j - s_i)\).
\(i\) and \(j\) are non-adjacent by Step ⟨3.1.2⟩, thus the product \(x_i x_j\) does not occur in \(f\), so \(f\) is linear in the shift.
⟨3.1.3⟩
ASSUME \(s_j \ge s_i\) without loss of generality, and shift all of \(x^*_i\) onto \(j\). By Step ⟨3.1.3⟩ the value does not decrease, yet the support loses the element \(i\), contradicting Step ⟨3.1.1⟩.
⟨3.1.4⟩
⟨3.1⟩
⊢ If the support of \(x \in \Delta_n\) is a clique \(K\) on \(k\) vertices, then \(f(x) \le 1 - 1/k\).
\(f(x) = \left(\sum_{i \in K} x_i\right)^2 - \sum_{i \in K} x_i^2\)
Every pair within the clique \(K\) is an edge and \(x\) vanishes off \(K\).
\(= 1 - \sum_{i \in K} x_i^2\)
We have \(\sum_{i \in K} x_i = 1\) because \(x\) is an element of the simplex.
\(\le 1 - 1/k\)
By Cauchy-Schwarz, \(k \sum_{i \in K} x_i^2 \ge \left(\sum_{i \in K} x_i\right)^2 = 1\), so \(\sum_{i \in K} x_i^2 \ge 1/k\).
⟨3.2⟩
By Step ⟨3.1⟩ a maximizer's support is a clique, of some size \(k \le \clq\), so Step ⟨3.2⟩ bounds the maximum by \(1 - 1/k \le 1 - 1/\clq\).
⟨3.3⟩
⟨3⟩
3.5. The probabilistic proof
Proof sketch.
Order the vertices uniformly at random and select every vertex that precedes all of its neighbors. The selected set is independent, and each \(v\) is selected with probability \(1/(\deg v + 1)\), so some independent set has size at least \(\sum_v 1/(\deg v + 1)\), the Caro-Wei bound [7, 8]. Applying this in the complement of a \(K_{r+1}\)-free graph and using convexity yields Turán's bound.
Proof of Theorem 1.2.
⊢ Every graph \(G\) has an independent set of size at least \(\sum_v \frac{1}{\deg v + 1}\).
PICK a uniformly random ordering \(\sigma\) of \(V(G)\), and WRITE \(I_\sigma\) for the set of vertices that appear before all of their neighbors.
⟨1.1⟩
⊢ \(I_\sigma\) is an independent set.
PICK two adjacent vertices \(v,w\) SUCH THAT \(\sigma(w) > \sigma(v)\). Since \(w\) does not precede all of its neighbors according to \(\sigma\), \(w \notin I_\sigma\).
⟨1.2⟩
⊢ \(\mathbb{E}|I_\sigma| = \sum_v \frac{1}{\deg v + 1}\).
Vertex \(v\) lands in \(I_\sigma\) exactly when it comes first among the \(\deg v + 1\) vertices consisting of \(v\) and its neighbors, an event of probability \(1/(\deg v + 1)\) by symmetry. Sum over \(v\) by linearity of expectation.
⟨1.3⟩
⟨1⟩
⊢ If \(G\) is \(K_{r+1}\)-free with \(m\) edges, then \(r \ge \sum_v \frac{1}{n - \deg v}\).
Apply Step ⟨1⟩ to the complement graph \(G^c\), in which \(v\) has degree \(n - 1 - \deg v\). An independent set of \(G^c\) is a clique of \(G\), so \(r \ge \clq(G) \ge \sum_v \frac{1}{n - \deg v}\).
⟨2⟩
⊢ \(\sum_v \frac{1}{n - \deg v} \ge \frac{n^2}{n^2 - 2m}\).
The function \(t \mapsto \frac{1}{n - t}\) is convex on the relevant range, so by Jensen's inequality the sum is at least \(\frac{n}{n - \bar{d}}\) where \(\bar{d} = 2m/n\) is the average degree.
⟨3⟩
Remark 3.3.
This argument proves the bound of equation (1.1) but not the exact statement \(\edges{G} \le \edges{\turan{n}}\), nor the uniqueness of the extremal graph: the convexity step is not tight for unbalanced degree sequences, and recovering exactness requires a separate argument.
4. From edges to eigenvalues
WRITE \(\mathbf{A}\) for the adjacency matrix of \(G\), and WRITE \(\specrad \ge \lambda_2 \ge \ldots \ge \lambda_n\) for its eigenvalues. Even with no hypothesis on \(G\), the largest eigenvalue is at least the average degree, so it already grows with the number of edges.
Lemma 4.1: Rayleigh bound
For every graph \(G\) with \(m\) edges, \(\specrad \ge 2m/n\).
Proof sketch.
Evaluate the Rayleigh quotient for \(\specrad\) at the all-ones vector \(\mathbf{1}\).
Proof.
\(\specrad = \max_{x \neq 0} \frac{x^{\top} \mathbf{A} x}{x^{\top} x}\).
The Rayleigh quotient characterization of the largest eigenvalue of a symmetric matrix.
⟨1⟩
Evaluate the quotient at the all-ones vector: \(\mathbf{1}^{\top} \mathbf{A} \mathbf{1} = 2m\) and \(\mathbf{1}^{\top} \mathbf{1} = n\), so \(\specrad \ge 2m/n\) by Step ⟨1⟩.
⟨2⟩
The Rayleigh bound is a lower bound on \(\specrad\). To constrain a graph we also need an upper bound; the first, in terms of the clique number, is Wilf's [9].
Theorem 4.2: Wilf (1986)
LET \(G\) be a graph with clique number \(\clq\). Then \(\specrad \le \left(1 - \frac{1}{\clq}\right) n\).
Proof.
PICK an eigenvector \(x\) for \(\specrad\) SUCH THAT \(x \ge 0\) and \(\sum_i x_i = 1\), so that \(x \in \Delta_n\). Then \(\specrad \sum_i x_i^2 = 2 \sum_{\{i,j\} \in E} x_i x_j\).
The adjacency matrix is symmetric with nonnegative entries, so \(\specrad\) has a nonnegative eigenvector (extend a Perron eigenvector of a component attaining \(\specrad\) by zeros); scale it to total weight one. Left-multiplying \(\mathbf{A}x = \specrad x\) by \(x^{\top}\) gives \(\specrad \sum_i x_i^2 = x^{\top} \mathbf{A} x = 2 \sum_{\{i,j\} \in E} x_i x_j\).
⟨1⟩
⊢ \(2 \sum_{\{i,j\} \in E} x_i x_j \le 1 - \frac{1}{\clq}\).
⟨2⟩
Wilf's bound is in terms of \(n\), while the Rayleigh bound is in terms of \(m\). Nikiforov sharpened Wilf to an upper bound in terms of \(m\) and \(\clq\).
Theorem 4.3: Nikiforov (2002)
LET \(G\) be a graph with \(m\) edges and clique number \(\clq\). Then
(4.1)
Proof sketch.
Write \(\specrad\) as the quadratic form at the unit Perron eigenvector, square it, and apply Cauchy-Schwarz over the edges. The squared weights again lie on the simplex, so Theorem 3.1 bounds the result [10].
Proof.
PICK an eigenvector \(x\) for \(\specrad\) SUCH THAT \(x \ge 0\) and \(\sum_i x_i^2 = 1\). Then \(\specrad = 2 \sum_{\{i,j\} \in E} x_i x_j\).
As in the proof of Theorem 4.2, Perron-Frobenius provides a nonnegative eigenvector, here scaled to unit norm; then \(\specrad = x^{\top} \mathbf{A} x\).
⟨1⟩
⊢ \(\specrad^2 \le 2m \cdot 2 \sum_{\{i,j\} \in E} x_i^2 x_j^2\).
Cauchy-Schwarz applied to the \(m\) summands of Step ⟨1⟩ gives \(\left(\sum_{\{i,j\} \in E} 2 x_i x_j \right)^2 \le m \sum_{\{i,j\} \in E} 4 x_i^2 x_j^2\).
⟨2⟩
⊢ \(2 \sum_{\{i,j\} \in E} x_i^2 x_j^2 \le 1 - \frac{1}{\clq}\).
The vector \(y\) with \(y_i = x_i^2\) lies on \(\Delta_n\) by the normalization of Step ⟨1⟩, so Theorem 3.1 applies to \(y\).
⟨3⟩
Both bounds are now in terms of \(m\). The Rayleigh bound gives \(2m/n \le \specrad\) and Nikiforov gives \(\specrad \le \sqrt{2m(1 - 1/\clq)}\); eliminating \(\specrad\) between them bounds \(m\) on its own.
The spectral statement is genuinely stronger than the edge count it implies. Its exact form identifies the Turán graph once more [11].
Theorem 4.5: Nikiforov (2007)
LET \(G\) be a \(K_{r+1}\)-free graph on \(n\) vertices. Then \(\specrad(G) \le \specrad(\turan{n})\), with equality if and only if \(G = \turan{n}\).
Proof sketch.
Unlike the bounds above, this does not reduce to Motzkin-Straus. It rests on the clique-count spectral inequality \(\specrad^r \le \sum_{s=2}^{r} (s-1) k_s(G) \specrad^{r-s}\) for \(K_{r+1}\)-free \(G\), where \(k_s(G)\) counts the \(s\)-cliques. By Zykov's theorem [4], \(k_s(G) < k_s(\turan{n})\) for \(2 \le s \le r\) unless \(G = \turan{n}\), so \(\specrad(G)\) is strictly less than the largest root of \(x^r = \sum_{s=2}^{r} (s-1) k_s(\turan{n}) x^{r-s}\). That is the characteristic equation of the Turán graph, whose largest root is \(\specrad(\turan{n})\). See [11] for the full proof.
This is the bound we have been studying from the start. The ceiling in Widget 1.1 is exactly the \(\specrad(\turan{n})\) of Theorem 4.5. The spectrum stays beneath it precisely while the graph is \(K_{r+1}\)-free, and the graphs that reach it are precisely the Turán graphs.
5. The open frontier
The passage from edge counts to eigenvalues is not a curiosity but an active research program. Spectral extremal graph theory asks, for each forbidden subgraph, how large the spectral radius can be, and a recurring discovery is that the classical extremal graph is spectral-extremal too: many Turán-type theorems carry eigenvalue strengthenings [11] that return the original edge count as a corollary. The bound of the previous section is one entry in this table; the broader questions in the circle of Bollobás and Nikiforov [12] remain a live source of problems.
The question turns markedly harder one dimension up. For 3-uniform hypergraphs the analogue of even the first case is open: Turán's conjecture that a \(K_4^{(3)}\)-free hypergraph, one with no four vertices spanning all four triples, has edge density at most \(5/9\) has stood since 1941, neither proved nor disproved, and Erdős offered a standing prize for the Turán density of complete hypergraphs. Razborov's flag-algebra method has driven the numerical upper bounds down toward the conjectured value, but exact hypergraph Turán densities remain the exception rather than the rule. The spectral thread of the previous section follows the problem upward as well: hypergraphs carry their own eigenvalues [13], so the spectral and the extremal questions meet again one dimension higher.
Even for graphs the picture is incomplete where the forbidden subgraph is bipartite. The Erdős-Stone-Simonovits theorem pins the extremal number of every non-bipartite subgraph to its chromatic number, but says only \(o(n^2)\) when that number is two, leaving the degenerate regime, the Turán numbers of even cycles, of complete bipartite graphs, and the Kővári-Sós-Turán problem, known only up to constants. A reader who has followed the five proofs and their spectral sequel has met most of the tools by which these frontiers are pried open.
The five proofs follow the canon collected by Aigner and Ziegler [14] and the modern treatment of Zhao [15]. This document was generated from a single plain-text source in the RSM language, a markup language for semantic research publishing; the toolchain and a guide to writing documents like this one are available at github.com/aris-pub/rsm.
References
1. Lamport, Leslie. "How to write a 21st century proof". Journal of Fixed Point Theory and Applications. 2012.
[↖1]
6. Motzkin, T. S. and Straus, E. G. "Maxima for graphs and a new proof of a theorem of Turán". Canadian Journal of Mathematics. 1965.
[↖1]
[↖1]
[↖1]
10. Nikiforov, V. "Some inequalities for the largest eigenvalue of a graph". Combinatorics, Probability and Computing. 2002.
[↖1]
12. Bollobás, B. and Nikiforov, V. "Cliques and the spectral radius". Journal of Combinatorial Theory, Series B. 2007.
[↖1]
13. Mulas, Raffaella and Zhang, Dong. "Spectral theory of Laplace operators on oriented hypergraphs". Discrete Mathematics. 2021.
[↖1]
15. Zhao, Y. "Graph Theory and Additive Combinatorics: Exploring Structure and Randomness". Cambridge University Press. 2023.
[↖1]