40.05.01 · combinatorics / extremal-ramsey

Extremal Graph Theory: Turán's Theorem and Erdős-Stone-Simonovits

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 7 (extremal graph theory: Turán, Erdős-Stone-Simonovits, the Kővári-Sós-Turán bound for bipartite H, the Erdős-Stone density and stability); Bollobás 1978 *Extremal Graph Theory* (Academic Press) Ch. I-VI (the complete theory of forbidden subgraphs, supersaturation, stability); the original sources Turán 1941, Erdős-Stone 1946, Erdős-Simonovits 1966 (the chromatic-number density formula), Simonovits 1968 (the stability theorem)

Intuition Beginner

Suppose you keep adding lines between dots, and you have made a private rule: you will never let three dots all be joined to one another, never a triangle. How many lines can you draw before you are forced to close one off? You feel a tension. Each new line is a chance for a triangle to appear, and the more lines already present, the harder it is to add a safe one. Extremal graph theory is the study of exactly this tension: the most lines you can fit while forbidding some shape.

The cleanest way to dodge a triangle is to split your dots into two teams and only draw lines between the teams, never inside a team. Two dots on the same team are never joined, so no triangle can form, since a triangle needs three dots all pairwise joined and any three dots put two on the same team. To squeeze in as many lines as you can, split the dots as evenly as possible into the two teams. This balanced two-team graph is the champion: it holds the record for triangle-free, and Mantel's theorem says its line count, about a quarter of all possible pairs, cannot be beaten.

What if you forbid a bigger fully-joined clump instead of a triangle? Then you split into more teams. Forbidding a clump of four dots, you use three teams; forbidding a clump of five, you use four. The record-holder is always the balanced split into one fewer team than the clump you banned. That graph carries a name: the Turán graph.

Visual Beginner

Picture six dots split into two teams of three: top team $a, b, c$ and bottom team $x, y, z$ . Draw every line that crosses between the teams and none inside a team. Each top dot joins all three bottom dots, giving $3 \times 3 = 9$ lines. No line sits inside a team, so no two same-team dots are joined, and any triangle would need two dots on one team — impossible. This is the balanced triangle-free champion on six dots.

The table records the nine crossing lines and checks the count against the record. Six dots have $(2 6) = 15$ possible pairs; the champion uses nine of them, which is the largest a triangle-free graph on six dots can reach.

team split	lines used	possible pairs	record?
3 and 3	9	15	yes
4 and 2	8	15	no
5 and 1	5	15	no

An uneven split, like four-and-two, drops to eight lines. The balanced split wins, which is why Mantel's record is about a quarter of all pairs: $9$ is close to $15/2$ rounded the favourable way, and exactly $⌊ 6^{2} /4 ⌋ = 9$ .

Worked example Beginner

Count the most lines on eight dots with no triangle, and check it against the formula. The formula from Mantel's theorem is $⌊ n^{2} /4 ⌋$ lines for $n$ dots.

Step 1. Apply the formula. With $n = 8$ , compute $8^{2} /4 = 64/4 = 16$ . So the record is $16$ lines.

Step 2. Build the champion. Split the eight dots into two teams of four, team $P = {1, 2, 3, 4}$ and team $Q = {5, 6, 7, 8}$ . Draw every line between a $P$ dot and a $Q$ dot.

Step 3. Count those lines. Each of the four $P$ dots joins each of the four $Q$ dots, so the number of crossing lines is $4 \times 4 = 16$ . This matches the formula exactly.

Step 4. Confirm no triangle. A triangle needs three dots, all pairwise joined. Any three of the eight dots place at least two in the same team, and same-team dots are never joined, so no triangle exists.

What this tells us: the balanced two-team graph hits the record $⌊ n^{2} /4 ⌋$ and stays triangle-free. The even split matters — a five-and-three split would give only $5 \times 3 = 15$ lines, one short of the record. Banishing a single shape forces a clean global structure on the densest survivor, and that structure is always a balanced multi-team graph.

Check your understanding Beginner

Formal definition Intermediate+

Let $H$ be a fixed graph. A graph $G$ is $H$ -free if it contains no copy of $H$ as a subgraph. The extremal number (or Turán number) $ex (n, H)$ is the maximum number of edges in an $H$ -free graph on $n$ vertices ^{[Diestel 2017 §7.1]}: $$ \operatorname{ex}(n, H) = \max{, |E(G)| : |V(G)| = n,\ G \text{ is } H\text{-free} ,}. $$ A graph attaining this maximum is an extremal graph for $H$ ; write $Ex (n, H)$ for the set of extremal graphs. The basic objects are the complete graphs $K_{r}$ (every pair joined) defined in 40.04.01 and the complete multipartite graphs.

The Turán graph $T_{r} (n)$ is the complete $r$ -partite graph on $n$ vertices whose parts $V_{1}, \dots, V_{r}$ are as equal as possible: each $∣ V_{i} ∣ \in {⌊ n / r ⌋, ⌈ n / r ⌉}$ , with all edges between distinct parts and none within a part. Its edge count is denoted $t_{r} (n) = ∣ E (T_{r} (n)) ∣$ . Because $T_{r} (n)$ is properly $r$ -coloured by its parts, it is $K_{r + 1}$ -free: a $K_{r + 1}$ would need $r + 1$ pairwise-adjacent vertices, hence $r + 1$ distinct parts. When $r ∣ n$ each part has $n / r$ vertices and $$ t_r(n) = \binom{n}{2} - r\binom{n/r}{2} = \left(1 - \frac{1}{r}\right)\frac{n^2}{2}, $$ and in general $t_{r} (n) = (1 - 1/ r) n^{2} /2 + O (1)$ . The case $r = 2$ gives $t_{2} (n) = ⌊ n^{2} /4 ⌋$ , the balanced complete bipartite graph $K_{⌊ n /2 ⌋, ⌈ n /2 ⌉}$ .

The chromatic number $χ (H)$ , from 40.04.06, is the least number of colour classes in a proper colouring of $H$ . A forbidden graph $H$ is degenerate (or bipartite-type) when $χ (H) = 2$ ; this is the regime where $ex (n, H) = o (n^{2})$ and the leading-order Turán behaviour collapses, requiring the separate Kővári-Sós-Turán analysis. For $χ (H) \geq 3$ the extremal density is governed by $χ (H)$ alone, the content of the Erdős-Stone-Simonovits theorem below.

Counterexamples to common slips

The extremal graph need not be unique away from the balanced point. For $K_{3}$ , $T_{2} (n)$ is the unique extremiser, but for bipartite $H$ many near-extremal graphs of very different structure coexist, since the leading term is $o (n^{2})$ and lower-order structure is not pinned down.
$ex (n, H)$ depends on $H$ only through $χ (H)$ to leading order — but only for $χ (H) \geq 3$ . For bipartite $H$ ( $χ (H) = 2$ ) the formula $(1 - 1/ (χ (H) - 1)) (2 n) = 0 \cdot (2 n)$ gives only $o (n^{2})$ , and the true order of growth (e.g. $n^{3/2}$ for $K_{2, 2} = C_{4}$ ) is not visible at this resolution.
Forbidding $H$ as a subgraph is not the same as forbidding it as an induced subgraph. Turán theory uses ordinary (not induced) containment: $T_{r} (n)$ contains many induced bipartite pieces but no $K_{r + 1}$ subgraph, which is all that is required.
Balance is forced, not optional. An unbalanced complete $r$ -partite graph is still $K_{r + 1}$ -free but has strictly fewer edges; moving a vertex from a larger part to a smaller one strictly increases the edge count, which is the engine of the symmetrisation proof.

Key theorem with proof Intermediate+

Theorem (Turán 1941). For every $n$ and every $r \geq 2$ , every $K_{r + 1}$ -free graph on $n$ vertices has at most $t_{r} (n)$ edges, and the unique extremal graph is the Turán graph $T_{r} (n)$ . In particular $ex (n, K_{r + 1}) = t_{r} (n)$ . (See ^{[Turán 1941]}, ^{[Diestel 2017 §7.1]}, ^{[West 2001 §5.2]}.)

Proof (Zykov symmetrisation). Let $G$ be a $K_{r + 1}$ -free graph on $n$ vertices with the maximum possible number of edges; we show $G ≅ T_{r} (n)$ . The argument shows first that non-adjacency is an equivalence relation on $V (G)$ , so $G$ is complete multipartite, and then that the parts are balanced.

For the first claim it suffices that whenever $u$ is non-adjacent to $v$ and $v$ is non-adjacent to $w$ , then $u$ is non-adjacent to $w$ ; reflexivity and symmetry are immediate. Suppose for contradiction that $u \neq \sim v$ , $v \neq \sim w$ , but the relation fails, in one of two ways.

First, suppose $d (v) < d (u)$ for some non-neighbour pair $u \neq \sim v$ . Delete $v$ and replace it by a clone $u^{'}$ of $u$ — a new vertex adjacent to exactly $N (u)$ . The result is still $K_{r + 1}$ -free: any $K_{r + 1}$ using $u^{'}$ would, since $u^{'}$ has the same neighbourhood as $u$ and $u^{'} \neq \sim u$ , give a $K_{r + 1}$ using $u$ in place of $u^{'}$ together with $u$ 's neighbours, which $G$ lacks. The new graph has $n$ vertices and $∣ E (G) ∣ - d (v) + d (u) > ∣ E (G) ∣$ edges, contradicting maximality. Hence in an extremal $G$ every non-neighbour pair has equal degree.

Now suppose $u \neq \sim v$ , $v \neq \sim w$ , but $u \sim w$ . If $d (u) > d (v)$ or $d (w) > d (v)$ the previous paragraph already gives a contradiction, so assume $d (u) = d (v) = d (w)$ . Delete both $u$ and $w$ and replace each by a clone of $v$ (two new vertices, each adjacent to $N (v)$ , non-adjacent to each other). This stays $K_{r + 1}$ -free for the same cloning reason, and the edge count changes by $- d (u) - d (w) + 1 + 2 d (v) = 1 > 0$ (the $+ 1$ is the lost edge $u w$ , and the two clones contribute $2 d (v)$ while $u, w$ removed $d (u) + d (w) = 2 d (v)$ ), again contradicting maximality. So non-adjacency is transitive.

Therefore $V (G)$ partitions into classes of mutually non-adjacent vertices with all cross-class edges present: $G$ is complete multipartite, say with parts $V_{1}, \dots, V_{s}$ . Since $G$ is $K_{r + 1}$ -free, $s \leq r$ , for $s$ parts contain a $K_{s}$ by choosing one vertex per part. Among complete $s$ -partite graphs on $n$ vertices the edge count $(2 n) - \sum_{i} (2 ∣ V _{i} ∣)$ is maximised by minimising $\sum_{i} (2 ∣ V _{i} ∣)$ ; this strictly decreases when a vertex moves from a part of size $\geq ∣ V_{j} ∣ + 2$ to a part $V_{j}$ , so the maximum forces all parts within one of each other and $s = r$ (a smaller $s$ admits adding an edge by splitting a part). The result is exactly $T_{r} (n)$ , and it is the unique extremiser. $□$

Bridge. Turán's theorem builds toward the entire density theory of forbidden subgraphs and appears again in the Erdős-Stone-Simonovits theorem, the probabilistic constructions of 40.07.01, and every Ramsey-type counting argument, because it converts a purely local prohibition — no $K_{r + 1}$ — into a rigid global structure, the balanced complete $r$ -partite graph. The foundational reason the symmetrisation works is the averaging principle inherited from 40.04.01: a maximal $K_{r + 1}$ -free graph cannot waste edges on a low-degree vertex when a high-degree clone is available, and this is exactly the weight-shifting that the Motzkin-Straus formulation phrases as a quadratic optimisation over the simplex. The complete-multipartite conclusion is dual to the chromatic reading of 40.04.06, since the Turán graph's parts are its colour classes, so $χ (T_{r} (n)) = r$ ; putting these together, forbidding $K_{r + 1}$ caps the density at the $r$ -colourable threshold, and the bridge to the asymptotic theory is the recognition that only $χ (H)$ , not $H$ itself, survives in the leading term.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Prove Mantel's theorem $ex (n, K_{3}) = ⌊ n^{2} /4 ⌋$ by the edge-counting argument: if $G$ is triangle-free then $d (u) + d (v) \leq n$ for every edge $uv$ .

Hint

For an edge $uv$ in a triangle-free graph, $N (u)$ and $N (v)$ are disjoint. Sum $d (u) + d (v)$ over all edges and apply Cauchy-Schwarz to $\sum d (v)^{2}$ .

Answer

If $uv \in E$ and $G$ is triangle-free, no vertex is adjacent to both $u$ and $v$ , so $N (u) \cap N (v) = \emptyset$ and $d (u) + d (v) = ∣ N (u) \cup N (v) ∣ \leq n$ . Summing over all edges, $\sum_{uv \in E} (d (u) + d (v)) = \sum_{v} d (v)^{2} \leq nm$ , where $m = ∣ E ∣$ and the left identity holds because each vertex $v$ appears in $d (v)$ edges contributing $d (v)$ each. By Cauchy-Schwarz, $\sum_{v} d (v)^{2} \geq (\sum_{v} d (v))^{2} / n = (2 m)^{2} / n$ . Combining, $(2 m)^{2} / n \leq nm$ , so $4 m^{2} \leq n^{2} m$ , giving $m \leq n^{2} /4$ , hence $m \leq ⌊ n^{2} /4 ⌋$ . The bound is attained by $K_{⌊ n /2 ⌋, ⌈ n /2 ⌉}$ . Rubric: full credit for the disjoint-neighbourhood bound, the degree-square sum identity, Cauchy-Schwarz, and the conclusion.

Exercise 5 (medium, short-answer).

Show that $t_{r} (n) \leq (1 - 1/ r) (2 n) \cdot \frac{n}{n - 1} = (1 - 1/ r) \frac{n ^{2}}{2}$ , and that the Turán graph maximises edges among all $K_{r + 1}$ -free complete multipartite graphs by a balancing argument.

Hint

Among complete $r$ -partite graphs the edge count is $(2 n) - \sum_{i} (2 n _{i})$ ; minimise $\sum_{i} (2 n _{i})$ subject to $\sum n_{i} = n$ by convexity.

Answer

A complete $r$ -partite graph with part sizes $n_{1}, \dots, n_{r}$ has $(2 n) - \sum_{i} (2 n _{i})$ edges, since the missing edges are exactly the within-part pairs. To maximise the edge count, minimise $\sum_{i} (2 n _{i}) = \frac{1}{2} \sum_{i} n_{i} (n_{i} - 1) = \frac{1}{2} (\sum_{i} n_{i}^{2} - n)$ , i.e. minimise $\sum_{i} n_{i}^{2}$ subject to $\sum_{i} n_{i} = n$ . The function $x \mapsto x^{2}$ is convex, so $\sum_{i} n_{i}^{2}$ is minimised when the $n_{i}$ are as equal as possible; if $n_{a} \geq n_{b} + 2$ , replacing $(n_{a}, n_{b})$ by $(n_{a} - 1, n_{b} + 1)$ changes $\sum n_{i}^{2}$ by $(n_{a} - 1)^{2} + (n_{b} + 1)^{2} - n_{a}^{2} - n_{b}^{2} = - 2 n_{a} + 2 n_{b} + 2 = - 2 (n_{a} - n_{b} - 1) < 0$ , a strict decrease. So balanced parts are forced, giving $T_{r} (n)$ , and the maximum edge count is $t_{r} (n) \leq (1 - 1/ r) n^{2} /2$ with equality up to the $O (1)$ rounding. Rubric: full credit for the edge identity, the convexity/exchange argument, and the bound.

Exercise 7 (hard, short-answer).

Prove the Kővári-Sós-Turán bound $ex (n, K_{2, 2}) = ex (n, C_{4}) = O (n^{3/2})$ . (This is the degenerate case $χ (C_{4}) = 2$ where Erdős-Stone-Simonovits gives only $o (n^{2})$ .)

Hint

Count "cherries" (paths of length two). A $C_{4}$ -free graph has at most one common neighbour for each vertex pair, so $\sum_{v} (2 d ( v )) \leq (2 n)$ .

Answer

Count pairs $({x, y}, v)$ where $v$ is a common neighbour of $x \neq = y$ — equivalently paths $x v y$ centred at $v$ . Centred at $v$ there are $(2 d ( v ))$ such pairs, so the total is $\sum_{v} (2 d ( v ))$ . If $G$ is $C_{4}$ -free then no two vertices have two common neighbours, so each pair ${x, y}$ is counted at most once: $\sum_{v} (2 d ( v )) \leq (2 n)$ . By convexity, $\sum_{v} (2 d ( v )) \geq n (2 d ˉ)$ where $\overset{ˉ}{d} = 2 m / n$ , so $n \cdot \frac{d ˉ ( d ˉ - 1 )}{2} \leq \frac{n ( n - 1 )}{2}$ , giving $\overset{ˉ}{d}^{2} - \overset{ˉ}{d} \leq n - 1$ , hence $\overset{ˉ}{d} \leq \frac{1 + 4 n - 3}{2} = O (n)$ . Then $m = n \overset{ˉ}{d} /2 = O (n^{3/2})$ . Rubric: full credit for the cherry count, the at-most-one-common-neighbour bound, convexity, and $O (n^{3/2})$ . (The Erdős-Rényi polarity graphs show this order is tight.)

Exercise 8 (hard, short-answer).

State and prove a supersaturation statement: for $K_{3}$ , show that a graph on $n$ vertices with $⌊ n^{2} /4 ⌋ + q$ edges (for $q \geq 1$ ) contains at least $q \cdot ⌊ n /2 ⌋$ triangles for $n$ large, or at least give the qualitative claim that the number of triangles grows linearly with the edge surplus.

Hint

Each extra edge beyond the Mantel threshold lies in many triangles. Use that removing one edge from each triangle would leave a triangle-free graph with at most $⌊ n^{2} /4 ⌋$ edges.

Answer

Qualitative claim: a graph $G$ on $n$ vertices with $m = ⌊ n^{2} /4 ⌋ + q$ edges contains at least $q$ triangles. Proof: if $G$ had fewer than $q$ triangles, pick one edge from each triangle and delete it; at most $q - 1$ edges are removed, leaving a graph $G^{'}$ that is triangle-free (every triangle lost an edge) with $∣ E (G^{'}) ∣ \geq m - (q - 1) = ⌊ n^{2} /4 ⌋ + 1 > ⌊ n^{2} /4 ⌋$ edges, contradicting Mantel's theorem. So $G$ has at least $q$ triangles. The stronger linear-in- $n$ bound follows from a stability / counting refinement (each surplus edge above the threshold creates order- $n$ triangles once $G$ is close to the extremal bipartite structure), which is the Erdős supersaturation phenomenon. Rubric: full credit for the delete-one-edge-per-triangle argument giving $\geq q$ triangles and a correct statement of the supersaturation upgrade.

Advanced results Master

Theorem (Erdős-Stone-Simonovits). For every fixed graph $H$ with chromatic number $χ (H) = r + 1 \geq 2$ , $$ \operatorname{ex}(n, H) = \left(1 - \frac{1}{\chi(H) - 1}\right)\binom{n}{2} + o(n^2) \qquad (n \to \infty). $$ Equivalently, the limiting edge density of an $H$ -free graph is $1 - 1/ (χ (H) - 1)$ . (Erdős-Stone ^{[Erdős, Stone 1946]}; Erdős-Simonovits ^{[Erdős, Simonovits 1966]}; Diestel ^{[Diestel 2017 §7.2]}.) The lower bound is the Turán construction of Exercise 6: $T_{r} (n)$ is $H$ -free with $(1 - 1/ r) (2 n) (1 + o (1))$ edges. The upper bound is the Erdős-Stone theorem proper, that for every $r$ and $t$ and every $ε > 0$ , a graph on $n$ vertices with at least $(1 - 1/ r + ε) (2 n)$ edges contains the complete $(r + 1)$ -partite graph $K_{r + 1} (t)$ with all parts of size $t$ , once $n$ is large; since any $H$ with $χ (H) = r + 1$ embeds in $K_{r + 1} (t)$ for $t = ∣ V (H) ∣$ , an $H$ -free graph cannot exceed the Turán density by any constant. The proof of the embedding is an iterated application of the minimum-degree averaging lemma of 40.04.01 together with a defect form of the Kővári-Sós-Turán counting: a dense graph has a dense subgraph of large minimum degree, inside which one greedily builds the $r + 1$ parts of size $t$ .

Theorem (the chromatic-number dichotomy). $ex (n, H) = o (n^{2})$ if and only if $H$ is bipartite ( $χ (H) = 2$ ); otherwise $ex (n, H) = Θ (n^{2})$ with the constant $1 - 1/ (χ (H) - 1) > 0$ . (Diestel ^{[Diestel 2017 §7.2]}.) The bipartite case is the degenerate regime: forbidding a bipartite $H$ allows only $o (n^{2})$ edges, and the precise order — between $n$ and $n^{2}$ — is the central open problem of degenerate extremal theory. The Kővári-Sós-Turán bound $ex (n, K_{s, t}) = O (n^{2 - 1/ s})$ for $s \leq t$ is the general degenerate upper bound, with matching lower-order constructions known only for $s \in {2, 3}$ and the diagonal $K_{t, t}$ asymptotics open. The forward reference to the co-produced Kővári-Sós-Turán unit develops this case in full.

Theorem (Simonovits stability). For every $H$ with $χ (H) = r + 1$ and every $ε > 0$ there is $δ > 0$ such that every $H$ -free graph on $n$ vertices with at least $ex (n, H) - δ n^{2}$ edges can be made into the Turán graph $T_{r} (n)$ by adding and deleting at most $ε n^{2}$ edges. (Simonovits 1968; Bollobás ^{[Bollobás 1978 Ch. VI]}.) Stability says the extremal graph is not merely optimal but robustly so: any graph close to the extremal edge count is close in edit distance to $T_{r} (n)$ . This converts the asymptotic density statement into a structural one and is the standard route to exact extremal results, where one first proves stability and then bootstraps to the exact Turán graph by a local refinement excluding the $o (n^{2})$ slack.

Theorem (supersaturation; Erdős-Simonovits). For every $H$ and every $ε > 0$ there is $c = c (ε, H) > 0$ such that every graph on $n$ vertices with at least $ex (n, H) + ε n^{2}$ edges contains at least $c \cdot n^{∣ V (H) ∣}$ copies of $H$ . (Erdős-Simonovits; Bollobás ^{[Bollobás 1978 Ch. VI]}.) Above the extremal threshold the number of forbidden copies does not merely become positive but jumps to a constant fraction of the maximum possible $Θ (n^{∣ V (H) ∣})$ . The proof averages the Erdős-Stone embedding over all $∣ V (H) ∣$ -subsets: a positive density of subsets each span a dense subgraph containing $H$ , so the count is $Ω (n^{∣ V (H) ∣})$ .

Synthesis. These results are one theory seen at increasing depth, and putting these together the extremal number $ex (n, H)$ , the Turán graph, and the chromatic number become three readings of how a forbidden subgraph constrains edge density. The central insight is that $χ (H)$ alone governs the leading term: this is exactly the content of Erdős-Stone-Simonovits, whose lower bound is Turán's balanced multipartite construction and whose upper bound is the embedding of a thick complete multipartite $K_{r + 1} (t)$ into any super-dense graph. The dichotomy between the dense regime $χ (H) \geq 3$ and the degenerate regime $χ (H) = 2$ is dual to the failure of the chromatic formula to resolve below the $o (n^{2})$ scale, where the Kővári-Sós-Turán bound takes over — the foundational reason bipartite forbidden subgraphs need the separate co-produced analysis. Stability generalises the optimality of $T_{r} (n)$ from a single extremiser to a basin of near-extremal graphs all close in edit distance, and supersaturation is the same threshold read from above, where the forbidden count jumps from zero to $Θ (n^{∣ V (H) ∣})$ ; the bridge is the Erdős-Stone embedding lemma, which simultaneously yields the upper density bound, the stability structure, and the supersaturation count, so the entire dense theory is one application of the averaging lemma of 40.04.01 iterated to extract a thick multipartite core.

Full proof set Master

Proposition 1 (Mantel's theorem). Every triangle-free graph on $n$ vertices has at most $⌊ n^{2} /4 ⌋$ edges, with equality only for $K_{⌊ n /2 ⌋, ⌈ n /2 ⌉}$ .

Proof. Let $G$ be triangle-free with $m$ edges and degree sequence $d (v)$ . For each edge $uv$ , the neighbourhoods $N (u), N (v)$ are disjoint (a common neighbour would form a triangle), so $d (u) + d (v) = ∣ N (u) \cup N (v) ∣ \leq n$ . Summing over edges, $\sum_{uv \in E} (d (u) + d (v)) = \sum_{v} d (v)^{2} \leq nm$ , since each $v$ is an endpoint of $d (v)$ edges and contributes $d (v)$ to each. By Cauchy-Schwarz, $\sum_{v} d (v)^{2} \geq \frac{( \sum _{v} d ( v ) ) ^{2}}{n} = \frac{( 2 m ) ^{2}}{n}$ . Hence $\frac{4 m ^{2}}{n} \leq nm$ , giving $m \leq n^{2} /4$ and so $m \leq ⌊ n^{2} /4 ⌋$ . Equality forces $d (u) + d (v) = n$ on every edge and a constant degree, which characterises the balanced complete bipartite graph. $□$

Proposition 2 (Turán's theorem, edge bound). Every $K_{r + 1}$ -free graph on $n$ vertices has at most $t_{r} (n)$ edges.

Proof (induction on $r$ , degree-maximal vertex). Induct on $n$ for fixed $r$ ; the base cases $n \leq r$ are direct since then $K_{r + 1}$ cannot occur and $G \subseteq K_{n} = T_{n} (n) \subseteq$ the appropriate Turán graph. For the step, let $G$ be $K_{r + 1}$ -free on $n$ vertices with the maximum edge count. Then $G$ contains a $K_{r}$ : otherwise $G$ is $K_{r}$ -free and by induction on $r$ has $\leq t_{r - 1} (n) < t_{r} (n)$ edges, fewer than the Turán construction, contradicting maximality. Let $A = {a_{1}, \dots, a_{r}}$ span a $K_{r}$ and $B = V ∖ A$ . Each vertex of $B$ has at most $r - 1$ neighbours in $A$ (an $r$ -th would complete a $K_{r + 1}$ with $A$ ), so the number of $A$ – $B$ edges is at most $(r - 1) (n - r)$ . Within $A$ there are $(2 r)$ edges. The induced graph $G [B]$ is $K_{r + 1}$ -free on $n - r$ vertices, so by the induction on $n$ it has at most $t_{r} (n - r)$ edges. Summing, $m \leq (2 r) + (r - 1) (n - r) + t_{r} (n - r)$ , and a direct computation shows the right side equals $t_{r} (n)$ (the Turán graph decomposes the same way: a part-transversal $K_{r}$ , the cross edges, and a smaller Turán graph). Hence $m \leq t_{r} (n)$ . $□$

Proposition 3 (uniqueness of the extremal graph). The unique $K_{r + 1}$ -free graph on $n$ vertices with $t_{r} (n)$ edges is $T_{r} (n)$ .

Proof. By the symmetrisation argument, an edge-maximal $K_{r + 1}$ -free graph has non-adjacency an equivalence relation, hence is complete multipartite with some $s \leq r$ parts. Among complete $s$ -partite graphs the edge count $(2 n) - \sum_{i} (2 n _{i})$ is strictly maximised, by the convex-exchange argument of Exercise 5, when the parts are balanced; and using $s < r$ parts is suboptimal because splitting any part of size $\geq 2$ into two parts adds edges while preserving $K_{r + 1}$ -freeness whenever the part count stays $\leq r$ . So $s = r$ and the parts are balanced: the graph is $T_{r} (n)$ . Since $T_{r} (n)$ achieves $t_{r} (n)$ and any other complete multipartite configuration is strictly smaller, the extremiser is unique. $□$

Proposition 4 (Motzkin-Straus formulation). For a graph $G$ with clique number $ω (G)$ , the maximum of $f (x) = \sum_{uv \in E} x_{u} x_{v}$ over the simplex $Δ = {x \geq 0 : \sum_{v} x_{v} = 1}$ equals $\frac{1}{2} (1 - \frac{1}{ω ( G )})$ .

Proof. Upper bound by construction: putting weight $1/ ω$ on each vertex of a maximum clique and $0$ elsewhere gives $f = (2 ω) / ω^{2} = \frac{1}{2} (1 - 1/ ω)$ , so the maximum is at least this. For the reverse, take a maximiser $x^{*}$ with the fewest nonzero coordinates and support $S$ . If two vertices $u, v \in S$ are non-adjacent, then $f$ is linear in $x_{u}, x_{v}$ along the line $x_{u} + x_{v} =$ const, so weight can be shifted entirely onto one of them without decreasing $f$ , reducing the support — against minimality. So $S$ spans a clique, $∣ S ∣ \leq ω$ , and on a clique $f (x) = \frac{1}{2} ((\sum_{v \in S} x_{v})^{2} - \sum_{v \in S} x_{v}^{2}) = \frac{1}{2} (1 - \sum x_{v}^{2}) \leq \frac{1}{2} (1 - 1/∣ S ∣) \leq \frac{1}{2} (1 - 1/ ω)$ , the inner inequality by Cauchy-Schwarz with equality at the uniform distribution. Hence the maximum is exactly $\frac{1}{2} (1 - 1/ ω)$ . Applying this with $ω \leq r$ for a $K_{r + 1}$ -free graph and $x_{v} = 1/ n$ recovers $m / n^{2} \leq \frac{1}{2} (1 - 1/ r)$ , i.e. Turán's edge bound. $□$

Proposition 5 (Erdős-Stone lower bound). For $χ (H) = r + 1 \geq 3$ , $ex (n, H) \geq (1 - 1/ r) \frac{n ^{2}}{2} + O (1)$ .

Proof. The Turán graph $T_{r} (n)$ has chromatic number exactly $r$ : its $r$ parts give a proper $r$ -colouring, and fewer than $r$ colours would assign two parts the same colour, but distinct parts are completely joined, so a monochromatic edge appears. A subgraph copy of $H$ inside $T_{r} (n)$ would force $χ (T_{r} (n)) \geq χ (H) = r + 1$ , contradicting $χ (T_{r} (n)) = r$ . Hence $T_{r} (n)$ is $H$ -free, and $ex (n, H) \geq t_{r} (n) = (1 - 1/ r) \frac{n ^{2}}{2} + O (1)$ . $□$

Proposition 6 (Kővári-Sós-Turán bound). For $1 \leq s \leq t$ , $ex (n, K_{s, t}) \leq \frac{1}{2} ((t - 1)^{1/ s} (n - s + 1) n^{1 - 1/ s} + (s - 1) n) = O (n^{2 - 1/ s})$ .

Proof. Let $G$ be $K_{s, t}$ -free with degrees $d (v)$ . Count pairs $(S, v)$ where $S$ is an $s$ -subset of $V$ and $v$ is adjacent to every vertex of $S$ — equivalently $S \subseteq N (v)$ . Centred at $v$ there are $(s d ( v ))$ such sets, so the total is $\sum_{v} (s d ( v ))$ . On the other hand, no $s$ -set $S$ has $t$ common neighbours (that would be a $K_{s, t}$ ), so each $S$ is counted at most $t - 1$ times: $\sum_{v} (s d ( v )) \leq (t - 1) (s n)$ . The function $x \mapsto (s x)$ is convex, so by Jensen $\sum_{v} (s d ( v )) \geq n (s d ˉ)$ with $\overset{ˉ}{d} = 2 m / n$ . Combining, $n (s d ˉ) \leq (t - 1) (s n)$ ; expanding the binomials and solving for $\overset{ˉ}{d}$ gives $\overset{ˉ}{d} \leq (t - 1)^{1/ s} n^{1 - 1/ s} + s$ , whence $m = n \overset{ˉ}{d} /2 = O (n^{2 - 1/ s})$ . The stated explicit bound follows by carrying the lower-order terms through the binomial expansion. $□$

Connections Master

Vertex colouring and the chromatic number 40.04.06. The Erdős-Stone-Simonovits theorem ties the entire extremal density to the chromatic number $χ (H)$ defined in that unit, since the Turán graph $T_{r} (n)$ has $χ (T_{r} (n)) = r$ exactly and the forbidden $H$ embeds in a dense graph as soon as the density passes the $r$ -colourable threshold. The clique-number bound $ω \leq χ$ developed there is the bridge: forbidding $K_{r + 1}$ caps $ω \leq r$ , and the Motzkin-Straus identity recasts Turán's bound as a maximisation whose value $\frac{1}{2} (1 - 1/ ω)$ reads off the clique number. Mycielski's gap between $ω$ and $χ$ from that unit is the extremal sibling showing why the degenerate bipartite case behaves so differently.
The probabilistic method: first moment and deletion 40.07.01. The lower-bound constructions matching the Kővári-Sós-Turán upper bound for bipartite forbidden subgraphs — random graphs with a few copies deleted, and the algebraic Erdős-Rényi polarity graphs — are produced by the first-moment and deletion methods developed there. Extremal upper bounds and probabilistic lower bounds are the two halves of pinning down $ex (n, H)$ : the counting argument here caps the edge density, and the random construction certifies it is essentially achieved, so the deletion method is the existence companion to Turán's optimisation.
The incidence algebra and Möbius inversion 40.02.02. The supersaturation and counting arguments in this unit are inclusion-exclusion over subgraph copies, the same Möbius machinery formalised there; counting $H$ -copies above the extremal threshold averages an indicator over all $∣ V (H) ∣$ -subsets, a sieve whose error terms are controlled by the partition-lattice Möbius function. The convexity (Jensen) steps in the Mantel and Kővári-Sós-Turán proofs are the analytic shadow of that combinatorial counting.
Kővári-Sós-Turán, regularity, and Ramsey [co-produced 40.05.02, 40.05.03, 40.05.04]. The degenerate bipartite case $χ (H) = 2$ , where this unit's formula gives only $o (n^{2})$ , is developed in the co-produced Kővári-Sós-Turán unit 40.05.02; the Szemerédi regularity lemma 40.05.03 supplies the modern proof of Erdős-Stone via the regularity-and-counting method and upgrades stability into the removal lemma; and Ramsey theory 40.05.04 is the dual extremal phenomenon, where instead of forbidding a subgraph one forces a monochromatic one, with the same Turán-graph constructions giving the lower bounds.

Historical & philosophical context Master

Extremal graph theory began with Pál Turán's 1941 paper On an extremal problem in graph theory (Matematikai és Fizikai Lapok 48) ^{[Turán 1941]}, written while Turán was in a labour camp; it generalised a 1907 observation of Willem Mantel that a triangle-free graph on $n$ vertices has at most $⌊ n^{2} /4 ⌋$ edges, and identified the balanced complete multipartite graph — now the Turán graph — as the unique extremiser for any forbidden complete graph. Turán's theorem is often cited as the founding result of the subject, the first to show that a local prohibition forces a precise global optimum. The Zykov symmetrisation proof used in the Key theorem section is due to Aleksandr Zykov in 1949, and the variational reformulation linking the independence number to a quadratic optimisation over the simplex is the 1965 theorem of Theodore Motzkin and Ernst Straus.

The asymptotic theory was opened by Paul Erdős and Arthur Stone in their 1946 paper On the structure of linear graphs (Bulletin of the American Mathematical Society 52) ^{[Erdős, Stone 1946]}, which proved that a graph of density exceeding the Turán threshold by any constant contains a large complete multipartite subgraph. Erdős and Miklós Simonovits drew the decisive corollary in their 1966 paper A limit theorem in graph theory (Studia Scientiarum Mathematicarum Hungarica 1) ^{[Erdős, Simonovits 1966]}: the leading term of $ex (n, H)$ is governed solely by the chromatic number $χ (H)$ , collapsing the extremal problem for every non-bipartite $H$ to its chromatic number. Simonovits added the stability theorem in 1968, showing near-extremal graphs are structurally close to the Turán graph, and the degenerate bipartite case was bounded by Tamás Kővári, Vera Sós, and Pál Turán in 1954. Béla Bollobás organised the mature theory in his 1978 monograph Extremal Graph Theory (Academic Press) ^{[Bollobás 1978]}.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{Bollobas1978,
  author    = {Bollob\'as, B\'ela},
  title     = {Extremal Graph Theory},
  publisher = {Academic Press},
  year      = {1978}
}

@book{West2001,
  author    = {West, Douglas B.},
  title     = {Introduction to Graph Theory},
  edition   = {2nd},
  publisher = {Prentice Hall},
  year      = {2001}
}

@article{Turan1941,
  author  = {Tur\'an, P\'al},
  title   = {On an extremal problem in graph theory},
  journal = {Matematikai \'es Fizikai Lapok},
  volume  = {48},
  year    = {1941},
  pages   = {436--452}
}

@article{ErdosStone1946,
  author  = {Erd\H{o}s, Paul and Stone, Arthur H.},
  title   = {On the structure of linear graphs},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {52},
  year    = {1946},
  pages   = {1087--1091}
}

@article{ErdosSimonovits1966,
  author  = {Erd\H{o}s, Paul and Simonovits, Mikl\'os},
  title   = {A limit theorem in graph theory},
  journal = {Studia Scientiarum Mathematicarum Hungarica},
  volume  = {1},
  year    = {1966},
  pages   = {51--57}
}

@article{KovariSosTuran1954,
  author  = {K\H{o}v\'ari, Tam\'as and S\'os, Vera T. and Tur\'an, P\'al},
  title   = {On a problem of K. Zarankiewicz},
  journal = {Colloquium Mathematicum},
  volume  = {3},
  year    = {1954},
  pages   = {50--57}
}

@article{MotzkinStraus1965,
  author  = {Motzkin, Theodore S. and Straus, Ernst G.},
  title   = {Maxima for graphs and a new proof of a theorem of Tur\'an},
  journal = {Canadian Journal of Mathematics},
  volume  = {17},
  year    = {1965},
  pages   = {533--540}
}

@article{Simonovits1968,
  author  = {Simonovits, Mikl\'os},
  title   = {A method for solving extremal problems in graph theory, stability problems},
  journal = {Theory of Graphs (Proc. Colloq. Tihany)},
  year    = {1968},
  pages   = {279--319}
}

Prerequisites

40.04.01

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §7.1 (the maximum number of edges, Turán's theorem) read for the half-the-pairs picture and the balanced-blocks construction; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §5.2 (Turán's theorem, Mantel) for the hand-drawn complete-multipartite extremal graphs; Aigner-Ziegler 2018 *Proofs from THE BOOK* (6th ed., Springer) Ch. on Turán for the small worked cases
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §7.1-§7.2 (the extremal number ex(n,H), Turán's theorem with the Zykov symmetrisation proof, the Erdős-Stone-Simonovits theorem); Bollobás 1998 *Modern Graph Theory* (Springer GTM 184) Ch. IV (extremal problems); West 2001 §5.2 (Mantel and Turán via weight-shifting and counting)
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 7 (extremal graph theory: Turán, Erdős-Stone-Simonovits, the Kővári-Sós-Turán bound for bipartite H, the Erdős-Stone density and stability); Bollobás 1978 *Extremal Graph Theory* (Academic Press) Ch. I-VI (the complete theory of forbidden subgraphs, supersaturation, stability); the original sources Turán 1941, Erdős-Stone 1946, Erdős-Simonovits 1966 (the chromatic-number density formula), Simonovits 1968 (the stability theorem)

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 7 (§7.1 the extremal number and Turán's theorem; §7.2 the Erdős-Stone theorem and the chromatic-number density formula; bipartite forbidden subgraphs and Kővári-Sós-Turán)
Bollobás 1978 — Extremal Graph Theory · Academic Press, 1978, Ch. I-VI (the extremal number ex(n,H), Turán's theorem, Erdős-Stone-Simonovits, supersaturation, the stability method)
West 2001 — Introduction to Graph Theory · 2nd ed., Prentice Hall, 2001, §5.2 (Mantel's theorem, Turán's theorem via weight-shifting and the counting / Zykov symmetrisation proofs, the Turán graph)
Turán 1941 — On an extremal problem in graph theory · Matematikai és Fizikai Lapok 48 (1941) 436-452 (in Hungarian); the K_{r+1}-free extremal theorem and the Turán graph T_r(n)
Erdős, Stone 1946 — On the structure of linear graphs · Bulletin of the American Mathematical Society 52 (1946) 1087-1091; ex(n, K_{r+1}(t)) = (1 - 1/r + o(1)) C(n,2), the supersaturation of complete multipartite subgraphs
Erdős, Simonovits 1966 — A limit theorem in graph theory · Studia Scientiarum Mathematicarum Hungarica 1 (1966) 51-57; the asymptotic ex(n,H) = (1 - 1/(chi(H)-1) + o(1)) C(n,2) governed by the chromatic number

Estimated time

beginner: 18m
intermediate: 50m
master: 88m