Turán's Theorem

Turán's theorem is one of the foundational results of extremal graph theory. It precisely determines the maximum number of edges in a graph on $n$ vertices that contains no complete subgraph $K_{r+1}$ , and characterizes the unique extremal graph.

Statement

Theorem4.1Turán's Theorem

For integers $n \geq r \geq 1$ , the maximum number of edges in a $K_{r+1}$ -free graph on $n$ vertices is $\operatorname{ex}(n, K_{r+1}) = t(n, r) = \left(1 - \frac{1}{r}\right)\frac{n^2}{2} - O(r).$ Moreover, the unique extremal graph is the Turán graph $T(n, r)$ , the complete $r$ -partite graph with part sizes as equal as possible.

Key Consequences

Definition4.2Chromatic Threshold

Turán's theorem implies that for any graph $H$ with $\chi(H) = r + 1$ , we have $\operatorname{ex}(n, H) \geq t(n, r)$ . The Erdos-Stone theorem sharpens this to $\operatorname{ex}(n, H) = t(n, r) + o(n^2)$ , establishing that the chromatic number determines the asymptotic Turán density of every non-bipartite graph.

Example$K_4$-Free Graphs

For $r = 3$ (forbidding $K_4$ ), the Turán graph $T(n, 3)$ is the complete 3-partite graph with parts of sizes $\lfloor n/3 \rfloor$ or $\lceil n/3 \rceil$ . The number of edges is $t(n, 3) = \frac{n^2}{3} - O(1).$ For example, $t(9, 3) = \binom{9}{2} - 3\binom{3}{2} = 36 - 9 = 27$ .

RemarkProof Strategy

The most elegant proof of Turán's theorem uses the method of Zykov symmetrization: among all $K_{r+1}$ -free graphs with the maximum number of edges, one can show that the extremal graph must be complete multipartite (replacing a non-adjacent pair of vertices by "merging" them). Among complete multipartite graphs, the balanced partition maximizes the edge count by the convexity argument.

Stability

Theorem4.2Simonovits Stability Theorem

For every graph $H$ with $\chi(H) = r + 1 \geq 3$ and every $\varepsilon > 0$ , there exists $\delta > 0$ such that if a $K_{r+1}$ -free graph $G$ on $n$ vertices has at least $t(n, r) - \delta n^2$ edges, then $G$ can be made into a copy of $T(n, r)$ by adding and deleting at most $\varepsilon n^2$ edges.

This stability result is powerful in applications: it says that near-extremal graphs must be close in edit distance to the Turán graph.

ExampleExact Results via Stability

To determine $\operatorname{ex}(n, H)$ exactly for specific graphs $H$ , one often first applies the Erdos-Stone theorem for asymptotics, then the stability theorem to narrow the structure, and finally a case analysis to pin down the exact extremal graph.