Extremal Graph Theory

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

(1 - \frac{1}{χ ( H ) - 1}) (2 n)

, 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.

Extremal graph theory asks: given a forbidden structure, how dense can a graph be before that structure is forced to appear? The canonical object is the Turán number $ex (n, H)$ , the maximum number of edges in an $n$ -vertex graph containing no subgraph isomorphic to $H$ . The field is unified by a startling phenomenon: for any graph $H$ that is not bipartite, the extremal density is governed solely by the chromatic number $χ (H)$ , so wildly different forbidden graphs can have identical asymptotic answers. The truly hard and beautiful cases are the degenerate ones — bipartite forbidden graphs — where even the order of magnitude of $ex (n, H)$ is often unknown (e.g. for $K_{4, 4}$ or even cycles). The surprising fact is that the extremal graph is essentially unique and highly structured: a balanced complete multipartite graph (the Turán graph), so an optimization problem with no symmetry imposed produces maximal symmetry as its answer.

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 $χ (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 $χ (H) = 2$ , where the construction is empty and the true count hides in lower-order, problem-specific algebraic and probabilistic structure.

Formal Statement

Turán Number and the Turán Graph

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

ex (n, H) = max {e (G) : ∣ V (G) ∣ = n, H \neq \subseteq G},

⟳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 \neq \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 $⌊ n / r ⌋$ or $⌈ n / r ⌉$ ). Its edge count is denoted $t (n, r) = e (T (n, r))$ . The symbols: $n$ = number of vertices, $r$ = number of parts, $χ (H)$ = chromatic number of $H$ , $K_{r}$ = complete graph on $r$ vertices, $K_{s, t}$ = complete bipartite graph.

Turán's Theorem (1941)

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

ex (n, K_{r}) = t (n, r - 1) = (1 - \frac{1}{r - 1}) \frac{n ^{2}}{2} - O (1),

⟳count edges of a complete

(r - 1)

-partite graph with balanced parts; with

n = (r - 1) q

, each of

(2 r - 1)

part-pairs contributes

q^{2}

edges, giving

(2 r - 1) q^{2} = \frac{r - 2}{2 ( r - 1 )} n^{2}

and the unique extremal graph is the Turán graph $T (n, r - 1)$ .

Erdős–Stone–Simonovits Theorem

For any fixed graph $H$ with $χ (H) = r \geq 2$ ,

ex (n, H) = (1 - \frac{1}{r - 1}) (2 n) + o (n^{2}) (n \to \infty) .

⟳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

π (H) := n \to \infty lim \frac{ex ( n , H )}{( 2 n )} = 1 - \frac{1}{χ ( H ) - 1} .

⟳divide [3] by

(2 n)

and take the limit; the

o (n^{2})

term vanishes, leaving the chromatic-number-dependent constant.

The Degenerate Case

When $χ (H) = 2$ (i.e. $H$ is bipartite), formula [4] gives $π (H) = 0$ , so the Erdős–Stone–Simonovits theorem reveals only that $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 $χ (H)$ and constitutes the central open problem of degenerate extremal graph theory. The general theorem is asymptotically silent here.

Why It Holds

Turá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 \neq \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) \geq d (u)$ and $d (v) \geq d (w)$ : delete both $u, w$ and replace by two clones of $v$ . Edge change is $2 d (v) - (d (u) + d (w)) - 1 \geq - 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 \leq 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)

e (G) = i < j \sum ∣ V_{i} ∣∣ V_{j} ∣ = \frac{1}{2} (n^{2} - i \sum ∣ V_{i} ∣^{2}),

⟳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 \leq r - 1$ parts is achieved at $k = r - 1$ balanced parts by Jensen/convexity. $□$

Erdős–Stone Upper Bound (sketch)

Goal: if

e (G) \geq (1 - \frac{1}{r - 1} + ε) (2 n)

then

G \supseteq K_{r} (t)

, the complete

r

-partite graph with

t

vertices per part, for

t = t (ε, r)

. Step 1. By repeated deletion of low-degree vertices, pass to a subgraph

G^{'}

of minimum degree

\geq (1 - \frac{1}{r - 1} + \frac{ε}{2}) ∣ 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

χ (H) = r

embeds into

K_{r} (t)

for

t \geq ∣ V (H) ∣

, the appearance of

K_{r} (t)

forces

H

. Hence above the Turán threshold

H

is unavoidable, proving [3].

□

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.

Building 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 $χ (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 ( $χ = 4$ ) have the same asymptotic Turán number — the extremal theory cannot tell them apart at the $n^{2}$ scale.

Turán density $\pi(H)=1-1/(\chi(H)-1)$ as a function of chromatic number

Worked Examples

Maximum triangle-free graph on 100 vertices

Given:

n = 100

, forbidden graph

H = K_{3}

(triangle), so

χ (K_{3}) = 3

r = 3

. Steps:

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

Answer:

ex (100, K_{3}) = 2500 edges

, uniquely realized by

K_{50, 50}

(Mantel's theorem).

Forbidding $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:

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

Answer:

ex (90, K_{4}) = 2700 edges

, uniquely realized by

T (90, 3) = K_{30, 30, 30}

Common Misconceptions

Chromatic number ≠ everything

A persistent error is concluding that because $π (H)$ depends only on $χ (H)$ , the entire extremal problem is settled by chromatic number. This is false at the second-order term: among graphs $H$ with the same $χ$ , the precise value of $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.

Even 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 $Θ (n^{3/2})$ edges." This is wrong. Forbidding $C_{4} = K_{2, 2}$ gives $ex (n, C_{4}) \sim \frac{1}{2} n^{3/2}$ (Kővári–Sós–Turán, tight via Erdős–Rényi polarity graphs). But forbidding $C_{6}$ gives $ex (n, C_{6}) = Θ (n^{4/3})$ and $C_{10}$ gives $Θ (n^{6/5})$ — different exponents entirely. In general $ex (n, C_{2 k}) = 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$ .

Connections

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 $π (K_{4}^{(3)})$ is unknown.

Real-World Applications

Property testing / theoretical CS: The triangle removal lemma (a corollary of regularity-driven extremal theory) underlies sublinear-time algorithms that test whether a huge graph is triangle-free without reading all of it.
Coding theory and combinatorial designs: $K_{s, t}$ -free extremal constructions (incidence structures of generalized quadrangles, projective planes) produce optimal codes and superconcentrators.
Network reliability and circuit complexity: Bounds on the size of graphs avoiding dense substructures give lower bounds on the number of gates in monotone Boolean circuits via the Razborov approximation method.
Additive number theory: The connection between $C_{4}$ -free graphs (Sidon sets / $B_{2}$ sequences) and extremal numbers gives the maximum size of a set of integers with all pairwise sums distinct.
Discrete geometry — unit distances: The Erdős unit-distance and distinct-distance problems are extremal problems on incidence graphs, bounded using $K_{2, t}$ -free arguments.
Database theory: Worst-case join-size bounds (the AGM bound) are extremal counts of homomorphisms generalizing Turán-type density estimates.
Data sparsification and spectral graph theory: Ramanujan and expander constructions arise as extremal graphs balancing edge count against absence of dense local structure.

Historical Development

1907 — Mantel's theorem. Willem Mantel proves the first extremal result: a triangle-free graph on $n$ vertices has at most $⌊ n^{2} /4 ⌋$ 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 $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 $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 $π (H) = 1 - 1/ (χ (H) - 1)$ ; the modern Erdős–Stone–Simonovits statement and the beginning of stability theory.
1974 — Bondy–Simonovits. Even-cycle bound $ex (n, C_{2 k}) = 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 $ex (n, K_{s, t}) = Θ (n^{2 - 1/ s})$ is tight for $t > (s - 1)!$ , a major degenerate breakthrough.

Subtleties & Limits

The central open problem of the field is the degenerate (bipartite) case. No general formula gives even the order of magnitude of

ex (n, H)

when

χ (H) = 2

Even cycles: Whether $ex (n, C_{2 k}) = Θ (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 \geq 4$ the truth of $ex (n, K_{t, t}) = Θ (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 $α \in [1, 2]$ is there a finite family $F$ with $ex (n, F) = Θ (n^{α})$ ? Recent work (Bukh–Conlon and others) resolves it for families but the single-graph version remains largely open.
Hypergraph Turán density: The value $π (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.