Extremal Graph Theory

⚡ Key Takeaways

Extremal graph theory studies the maximum or minimum value of a graph parameter (typically the number of edges) over all graphs satisfying a prescribed structural constraint — usually the absence of a fixed subgraph. The flagship result, the Erdős–Stone–Simonovits theorem, says that the maximum edge density of an $n$ -vertex graph with no copy of $H$ is asymptotically $\left(1-\tfrac{1}{\chi(H)-1}\right)\binom{n}{2}$ , determined entirely by the chromatic number of $H$ . It applies across combinatorics, theoretical computer science, number theory, and discrete geometry. Founded by Turán (1941) building on Mantel (1907), with the asymptotic theory completed by Erdős, Stone, and Simonovits.

💡 The Core Insight

Forbidding a subgraph $H$ forces global sparsity, and the amount of sparsity is dictated by the local obstruction of chromatic number. To avoid an $H$ with $\chi(H)=r$ , the cheapest way to use many edges is to partition vertices into $r-1$ classes and join all pairs across classes: this contains no $K_r$ (hence no $H$ ) yet maximizes edges. The depth of the theory lies in (a) proving this multipartite construction is optimal, not merely good, and (b) understanding what happens when $\chi(H)=2$ , where the construction is empty and the true count hides in lower-order, problem-specific algebraic and probabilistic structure.

DefinitionTurán Number and the Turán Graph

Let $H$ be a fixed graph. The Turán number (or extremal number) is

1

\quad \mathrm{ex}(n,H) \;=\; \max\Big\{\, e(G) \;:\; |V(G)|=n,\; H \not\subseteq G \,\Big\},

Derivation hint: maximize the edge count $e(G)$ over the finite set of all $H$ -free labeled graphs on $n$ vertices; the max exists by finiteness. where $e(G)$ is the number of edges of $G$ and $H \not\subseteq G$ means $G$ contains no (not necessarily induced) subgraph isomorphic to $H$ . A graph attaining the maximum is an extremal graph for $(n,H)$ . The Turán graph $T(n,r)$ is the complete $r$ -partite graph on $n$ vertices with part sizes as equal as possible (each of size $\lfloor n/r\rfloor$ or $\lceil n/r\rceil$ ). Its edge count is denoted $t(n,r) = e(T(n,r))$ . The symbols: $n$ = number of vertices, $r$ = number of parts, $\chi(H)$ = chromatic number of $H$ , $K_r$ = complete graph on $r$ vertices, $K_{s,t}$ = complete bipartite graph.

TheoremTurán's Theorem (1941)

For every $n\ge 1$ and $r\ge 2$ ,

2

\quad \mathrm{ex}(n,K_r) \;=\; t(n,r-1) \;=\; \Big(1-\tfrac{1}{r-1}\Big)\frac{n^2}{2}\;-\;O(1),

Derivation hint: count edges of a complete $(r-1)$ -partite graph with balanced parts; with $n=(r-1)q$ , each of $\binom{r-1}{2}$ part-pairs contributes $q^2$ edges, giving $\binom{r-1}{2}q^2 = \tfrac{r-2}{2(r-1)}n^2$ . and the unique extremal graph is the Turán graph $T(n,r-1)$ .

TheoremErdős–Stone–Simonovits Theorem

For any fixed graph $H$ with $\chi(H)=r\ge 2$ ,

3

\quad \mathrm{ex}(n,H) \;=\; \Big(1-\frac{1}{r-1}\Big)\binom{n}{2}\;+\;o(n^2)\qquad (n\to\infty).

Derivation hint: lower bound from $T(n,r-1)$ being $H$ -free (it is $(r-1)$ -colorable, $H$ needs $r$ colors); upper bound from the Erdős–Stone theorem, which forces a large complete $r$ -partite subgraph hence a copy of $H$ once density exceeds the Turán threshold. Equivalently, the Turán density is

4

\quad \pi(H) \;:=\; \lim_{n\to\infty}\frac{\mathrm{ex}(n,H)}{\binom{n}{2}} \;=\; 1-\frac{1}{\chi(H)-1}.

Derivation hint: divide [3] by $\binom{n}{2}$ and take the limit; the $o(n^2)$ term vanishes, leaving the chromatic-number-dependent constant.

⚠️ The Degenerate Case

When $\chi(H)=2$ (i.e. $H$ is bipartite), formula [4] gives $\pi(H)=0$ , so the Erdős–Stone–Simonovits theorem reveals only that $\mathrm{ex}(n,H)=o(n^2)$ . The true order of growth — whether $n^{3/2}$ , $n^{5/3}$ , or something else — is not determined by $\chi(H)$ and constitutes the central open problem of degenerate extremal graph theory. The general theorem is asymptotically silent here.

ProofTurán's Theorem via Zykov Symmetrization

We show that among $K_r$ -free graphs on $n$ vertices, $T(n,r-1)$ maximizes edges.

Step 1 — Reduce to complete multipartite graphs. Let $G$ be edge-maximal $K_r$ -free. Claim: the relation " $u \sim v$ iff $u,v$ non-adjacent" is an equivalence relation on $V(G)$ , which forces $G$ to be complete multipartite. It suffices to show non-adjacency is transitive.

Step 2 — Symmetrization. Suppose $x \not\sim$ -relate fails: say $u,v$ non-adjacent, $v,w$ non-adjacent, but $u,w$ adjacent. Compare degrees.

If $d(u) > d(v)$ : delete $v$ , replace it by a clone $u'$ of $u$ (same neighborhood as $u$ ). This cannot create a $K_r$ (the two copies $u,u'$ are non-adjacent so no clique uses both), and the new graph has more edges. Contradiction with maximality.
Symmetrically if $d(w) > d(v)$ , clone $w$ .
If $d(v) \ge d(u)$ and $d(v) \ge d(w)$ : delete both $u,w$ and replace by two clones of $v$ . Edge change is $2d(v) - (d(u)+d(w)) - 1 \ge -1$ ...

Step 3 — The clean argument (Motzkin–Straus / direct count). A cleaner route: since $G$ is complete multipartite with parts $V_1,\dots,V_k$ and is $K_r$ -free, we need $k\le r-1$ . With $k$ parts fixed, edge count is maximized by balancing part sizes (convexity: moving a vertex from a smaller part to a larger part among non-balanced parts strictly increases edges). Hence $k=r-1$ balanced, i.e. $G=T(n,r-1)$ .

5

\quad e(G)=\sum_{i<j}|V_i||V_j|=\frac{1}{2}\Big(n^2-\sum_i |V_i|^2\Big),

Derivation hint: total ordered adjacent pairs $=n^2-\sum|V_i|^2$ since within-part pairs are non-edges; divide by 2 for unordered edges. Minimizing $\sum_i |V_i|^2$ subject to $\sum_i|V_i|=n$ and $k\le r-1$ parts is achieved at $k=r-1$ balanced parts by Jensen/convexity. $\square$

∎

ProofErdős–Stone Upper Bound (sketch)

Goal: if $e(G) \ge \big(1-\tfrac1{r-1}+\varepsilon\big)\binom n2$ then $G \supseteq K_{r}(t)$ , the complete $r$ -partite graph with $t$ vertices per part, for $t=t(\varepsilon,r)$ .

Step 1. By repeated deletion of low-degree vertices, pass to a subgraph $G'$ of minimum degree $\ge \big(1-\tfrac1{r-1}+\tfrac\varepsilon2\big)|V(G')|$ on still-linear vertex count.

Step 2. Induct on $r$ . By induction $G'$ contains $K_{r-1}(s)$ with $s$ large. Its $(r-1)s$ vertices each have huge degree; a counting/pigeonhole argument finds a set of $t$ common neighbors avoiding the existing blob, building the $r$ -th part.

Step 3. Since any fixed $H$ with $\chi(H)=r$ embeds into $K_r(t)$ for $t \ge |V(H)|$ , the appearance of $K_r(t)$ forces $H$ . Hence above the Turán threshold $H$ is unavoidable, proving [3]. $\square$

∎

mathematician · Pál Turán | 1910–1976

Hungarian mathematician whose 1941 paper, written while interned in a forced-labor camp during World War II, founded extremal graph theory. Turán reportedly worked out the theorem mentally, lacking paper, and was motivated by a question of his friend... his result generalized Mantel's 1907 triangle bound and crystallized the idea that forbidding cliques imposes precise quantitative density limits. Turán was a number theorist by training (the Turán sieve, power-sum method) and viewed his graph theorem as a curiosity until Erdős championed extremal combinatorics into a major discipline. The collaboration of Turán with Erdős and the later students (Simonovits, Szemerédi) made Hungary the heartland of the subject.

🧠 Intuition

Think of edges as a budget and the forbidden graph $H$ as a tripwire. To spend the most edges without tripping a $K_r$ , you cluster vertices into $r-1$ "color classes," forbid edges inside a class (those are wasted, since they could complete a clique), and lavish all spending on edges between classes. Balancing class sizes is just the AM–QM inequality: equal parts minimize $\sum |V_i|^2$ , which by [5] maximizes edges. The chromatic number $\chi(H)$ enters because $H$ is $r$ -chromatic exactly when it cannot be drawn inside an $(r-1)$ -partite graph — so the $(r-1)$ -partite Turán graph is precisely "as dense as possible while remaining a place $H$ can never live." Erdős–Stone is the surprising converse: any graph even slightly denser than the Turán graph must contain a blown-up clique $K_r(t)$ , a structure so rich it harbors every $r$ -chromatic $H$ . This is why two forbidden graphs as different as $K_5$ and the icosahedron ( $\chi=4$ ) have the same asymptotic Turán number — the extremal theory cannot tell them apart at the $n^2$ scale.

Figure

Turán density

\pi(H)=1-1/(\chi(H)-1)

as a function of chromatic number

ExampleMaximum triangle-free graph on 100 vertices

Given: $n=100$ , forbidden graph $H=K_3$ (triangle), so $\chi(K_3)=3$ , $r=3$ .

Steps: 1. By Turán's theorem [2], $\mathrm{ex}(100,K_3)=t(100,2)$ , edges of the balanced complete bipartite graph $K_{50,50}$ . 2. Compute: $e(K_{50,50}) = 50\times 50 = 2500$ . 3. Check via [5]: $\tfrac12(100^2 - (50^2+50^2)) = \tfrac12(10000-5000)=2500$ . ✓ 4. Compare to total possible edges $\binom{100}{2}=4950$ ; the density ratio is $2500/4950 \approx 0.505$ , matching $\pi(K_3)=1-\tfrac{1}{2}=\tfrac12$ .

Answer: $\boxed{\mathrm{ex}(100,K_3)=2500 \text{ edges}}$ , uniquely realized by $K_{50,50}$ (Mantel's theorem).

ExampleForbidding

K_4

on 90 vertices

Given: $n=90$ , $H=K_4$ , so $r=4$ , extremal graph is $T(90,3)$ — complete tripartite with three equal parts of $30$ .

Steps: 1. Part sizes: $90/3 = 30$ each, perfectly balanced. 2. Edges between each pair of parts: $30 \times 30 = 900$ ; there are $\binom{3}{2}=3$ pairs. 3. Total: $3 \times 900 = 2700$ . 4. Verify the asymptotic formula [2]: $\big(1-\tfrac13\big)\tfrac{90^2}{2} = \tfrac23 \cdot \tfrac{8100}{2}=\tfrac23 \cdot 4050 = 2700$ . Exact because $n$ is divisible by $r-1=3$ .

Answer: $\boxed{\mathrm{ex}(90,K_4)=2700 \text{ edges}}$ , uniquely realized by $T(90,3)=K_{30,30,30}$ .

⚠️ Chromatic number ≠ everything

A persistent error is concluding that because $\pi(H)$ depends only on $\chi(H)$ , the entire extremal problem is settled by chromatic number. This is false at the second-order term: among graphs $H$ with the same $\chi$ , the precise value of $\mathrm{ex}(n,H)$ (including the $o(n^2)$ correction and the exact extremal graph) varies, and is governed by finer invariants such as the decomposition family and the structure of the color-critical edges (Simonovits's stability theory). Moreover, for bipartite $H$ the chromatic number gives zero information about the growth rate.

CounterexampleEven cycles defeat the naive guess

One might guess that since the Petersen graph and $K_{3,3}$ are both forbidden structures, "forbidding any fixed bipartite graph gives $\Theta(n^{3/2})$ edges." This is wrong. Forbidding $C_4=K_{2,2}$ gives $\mathrm{ex}(n,C_4) \sim \tfrac12 n^{3/2}$ (Kővári–Sós–Turán, tight via Erdős–Rényi polarity graphs). But forbidding $C_6$ gives $\mathrm{ex}(n,C_6)=\Theta(n^{4/3})$ and $C_{10}$ gives $\Theta(n^{6/5})$ — different exponents entirely. In general $\mathrm{ex}(n,C_{2k})=O(n^{1+1/k})$ , with matching lower bounds known only for $k=2,3,5$ . The growth exponent is sensitive to the precise bipartite graph, not a universal $3/2$ .

connection

Extremal graph theory connects deeply to its neighbors. The upper bound machinery of Erdős–Stone is most naturally proved via the Szemerédi Regularity Lemma, which partitions any dense graph into quasi-random pieces; the removal lemma derived from it underlies modern proofs of Roth's Theorem on Arithmetic Progressions. The degenerate (bipartite) case is intimately tied to the Zarankovic Problem and incidence geometry — the Kővári–Sós–Turán bound for $K_{s,t}$ -free graphs is identical to counting point–line incidences. The probabilistic lower-bound constructions belong to the Probabilistic Method, and the algebraic constructions (norm graphs, projective planes) link to Finite Geometry and Algebraic Combinatorics. The hypergraph generalization opens onto Hypergraph Turán Problem, where even $\pi(K_4^{(3)})$ is unknown.

🔬 Where this appears

⏳ History

- 1907 — Mantel's theorem. Willem Mantel proves the first extremal result: a triangle-free graph on

n

vertices has at most

\lfloor n^2/4\rfloor

edges. This is the

r=3

case of Turán.

- 1938 — Erdős, Sidon sequences. Paul Erdős studies

B_2

sets, implicitly extremal graph problems, and meets the bipartite degenerate phenomenon.

- 1941 — Turán's theorem. Pál Turán determines

\mathrm{ex}(n,K_r)

exactly and proves uniqueness of the extremal Turán graph, founding the field.

- 1946 — Kővári–Sós–Turán. Tamás Kővári, Vera T. Sós, and Pál Turán bound

\mathrm{ex}(n,K_{s,t})=O(n^{2-1/s})

, opening the degenerate theory.

- 1946 — Erdős–Stone theorem. Erdős and Arthur Stone prove the asymptotic density for

K_r(t)

, the engine of the general theory.

- 1966 — Erdős–Simonovits. Reformulation making explicit that

\pi(H)=1-1/(\chi(H)-1)

; the modern Erdős–Stone–Simonovits statement and the beginning of stability theory.

- 1974 — Bondy–Simonovits. Even-cycle bound

\mathrm{ex}(n,C_{2k})=O(n^{1+1/k})

, sharpening degenerate understanding.

- 1975 — Szemerédi Regularity Lemma. Endre Szemerédi's lemma gives a uniform, structural proof technique that subsumes Erdős–Stone and powers extremal/removal-lemma results.

- 1996 — Kollár–Rónyai–Szabó & Alon–Rónyai–Szabó. Norm-graph constructions show

\mathrm{ex}(n,K_{s,t})=\Theta(n^{2-1/s})

is tight for

t > (s-1)!

, a major degenerate breakthrough.

open-problem

The central open problem of the field is the degenerate (bipartite) case. No general formula gives even the order of magnitude of $\mathrm{ex}(n,H)$ when $\chi(H)=2$ .

Even cycles: Whether $\mathrm{ex}(n,C_{2k})=\Theta(n^{1+1/k})$ holds for all $k$ is open; matching lower bounds are known only for $k\in\{2,3,5\}$ .
Complete bipartite $K_{t,t}$ : For $t\ge 4$ the truth of $\mathrm{ex}(n,K_{t,t})=\Theta(n^{2-1/t})$ is unknown; constructions matching the KST upper bound exist only when one side is large relative to the other.
Rational exponents conjecture (Erdős–Simonovits): For every rational $\alpha\in[1,2]$ is there a finite family $\mathcal F$ with $\mathrm{ex}(n,\mathcal F)=\Theta(n^\alpha)$ ? Recent work (Bukh–Conlon and others) resolves it for families but the single-graph version remains largely open.
Hypergraph Turán density: The value $\pi(K_4^{(3)})$ — the simplest unsolved hypergraph Turán problem, conjectured by Turán to be $5/9$ — has been open since 1941, despite intense effort and flag-algebra bounds.

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also