Turán's Theorem: The Densest Triangle-Free Graph

The precise statement

Fix integers n ≥ 1 and r ≥ 2. Let G be a simple graph on n vertices containing no clique K_r+1 (no r+1 mutually adjacent vertices). Turán's theorem asserts

• e(G) ≤ (1 − 1/r)·n²/2, and
• equality holds if and only if G is the Turán graph T(n, r).

The Turán graph T(n, r) is the complete r-partite graph whose parts are as equal as possible: partition the n vertices into r blocks of sizes ⌊n/r⌋ or ⌈n/r⌉, and join two vertices exactly when they lie in different blocks. It is K_r+1-free because a clique can use at most one vertex per part.

Two hypotheses do the work: G is simple and finite, and the forbidden object is a complete graph K_r+1. When n is divisible by r the bound is exactly (1 − 1/r)·n²/2; otherwise the true maximum is e(T(n, r)), which the closed form slightly rounds. The r = 2 case gives ⌊n²/4⌋, Mantel's theorem.

The picture: why balance wins

The intuition is a tension between two forces. To avoid a K_r+1, you must leave the vertices r-colorable at the clique level — no r+1 pairwise-linked vertices. The most edges you can afford under that constraint come from an r-partite structure: split into r independent groups and connect everything across groups. That already forbids K_r+1 for free.

Given that you'll be r-partite, how big should the parts be? The number of cross-edges is maximized when the parts are as equal as possible. This is a convexity fact: if one part has a vertices and another has b > a, moving a vertex from the big part to the small part changes the edge count by (b − 1) − a > 0 whenever b > a + 1, so imbalance always loses edges.

• Avoiding the clique pushes you to r-partite.
• Maximizing density pushes the parts toward equal size.

The Turán graph is the unique configuration that satisfies both — the densest possible graph that still dodges K_r+1.

The key idea of the proof

Several proofs exist; the cleanest is Zykov's symmetrization (weight-shifting), which turns any extremal graph into a Turán graph. Take a K_r+1-free graph G with the maximum number of edges. Call two vertices equivalent if they are non-adjacent. The trick is:

• If u and v are non-adjacent, we may replace v by a clone of u (delete v's edges, copy u's neighborhood onto v) without creating a K_r+1 and without losing edges — otherwise u or v had strictly fewer neighbors, contradicting maximality after cloning the higher-degree one.
• If u and v are non-adjacent and w is adjacent to both, one checks a degree comparison forces non-adjacency to be an equivalence relation on an extremal G.

Non-adjacency being an equivalence relation means the vertices partition into independent sets that are completely joined to each other — G is complete multipartite. Since G is K_r+1-free it has at most r parts, and the convexity argument forces the parts to be balanced. Hence G = T(n, r). An alternative induction removes a maximum clique K_r and bounds the rest; a third proof uses Cauchy–Schwarz on the degree sequence via ∑ d(v) counted over non-edges.

Worked example: r = 2, the triangle-free case

Take n = 6 and forbid triangles (r = 2). Turán's bound gives (1 − 1/2)·6²/2 = 9 edges. The extremal graph is T(6, 2) = K_3,3: split six vertices into two blocks {a,b,c} and {x,y,z} and connect every a-type vertex to every x-type vertex. That's 3 × 3 = 9 edges, and it is genuinely triangle-free since any triangle would need two vertices in one block, but those two are non-adjacent.

Can you do better with 10 edges on 6 vertices? No — any 10-edge graph on six vertices must contain a triangle. And unbalanced bipartite graphs lose: K_2,4 has only 2 × 4 = 8 edges, one short of the balanced K_3,3. For odd n, say n = 7, the maximum is ⌊49/4⌋ = 12 = 3 × 4 = e(K_3,4).

For r = 3, n = 6: the bound is (2/3)·36/2 = 12 edges, achieved by T(6,3) = K_2,2,2 (the octahedron), which has no K₄.

Where the hypotheses bite, and connections

The forbidden graph must be complete. Turán's clean bound is a clique phenomenon. If you instead forbid a bipartite graph like K_s,t, the answer collapses: by the Kővári–Sós–Turán theorem the maximum is only O(n^2−1/s) = o(n²) edges, a completely different, sub-quadratic regime where the extremal graphs are not Turán graphs at all (they come from incidence geometry and are notoriously hard to pin down exactly).

The chromatic number is what matters asymptotically. The Erdős–Stone theorem (1946) generalizes Turán: for any fixed graph H with chromatic number χ(H) = r+1, the maximum edge count is (1 − 1/r + o(1))·n²/2. So Turán's exact bound is the leading term of the whole extremal picture; the o(n²) error only vanishes cleanly when H is itself a clique.

• Turán is the exact, non-asymptotic case χ(H) = r+1 with H = K_r+1.
• Erdős–Stone extends it to all non-bipartite H, up to a lower-order error.

Why it matters

Turán's theorem founded extremal graph theory — the systematic study of how a forbidden local structure forces a global density ceiling. It set the template of forbidden subgraph → sharp edge bound → unique extremal example that recurs throughout the subject.

• Ramsey theory: Turán-type density bounds feed lower-bound constructions and interact with Ramsey numbers; the triangle-free extremal graph shows you can pack ~n²/4 edges without a triangle.
• Additive combinatorics: the Kruskal–Katona and Turán-density machinery underlies results on sum-free sets and independent sets.
• Hypergraph Turán problems: the analogue for 3-uniform hypergraphs (e.g. the Turán density of K₄⁽³⁾) is a famous open problem — Turán's own conjecture — showing how deep the innocent-looking question runs.
• Spectral and probabilistic methods: the theorem admits proofs via eigenvalue bounds (Wilf, Motzkin–Straus) linking clique number to the largest eigenvalue and to a quadratic optimization over the simplex.

Its worked identity Motzkin–Straus — max of ∑_ij∈E x_ix_j over the probability simplex equals ½(1 − 1/ω(G)) — even reframes clique number as a continuous optimization.

Turán's theorem versus Mantel's theorem and the asymptotic Erdős–Stone refinement

Result	Forbidden subgraph	Max edges	Extremal graph
Mantel (1907)	K₃ (triangle)	⌊n²/4⌋	K_{⌊n/2⌋,⌈n/2⌉} (balanced bipartite)
Turán (1941)	K_{r+1}	(1 − 1/r)·n²/2	T(n, r) (balanced r-partite)
Erdős–Stone (1946)	Any H with χ(H)=r+1	(1 − 1/r + o(1))·n²/2	Asymptotically T(n, r)
Kővári–Sós–Turán (1954)	K_{s,t} (bipartite)	O(n^{2−1/s})	Incidence-type, non-Turán