Chapter 19: Extremal Graph Theory

Turán's Theorem (1941). For integers $r \ge 1$ and $n \ge 1$, the maximum edge count of any $K_{r+1}$-free graph on $n$ vertices is exactly:

Up to vertex relabeling, the unique extremal graph attaining this maximum is the Turán graph $T_r(n)$. When $n = rq + s$ with $0 \le s < r$, there are $s$ parts of size $q+1$ and $r-s$ parts of size $q$, yielding:

Proof via Zykov Symmetrization (Cloning). Among all $K_{r+1}$-free graphs on $n$ vertices with maximum edge count, pick $G$ maximizing the secondary quantity $\sum_v d(v)^2$. If two nonadjacent vertices $u, v$ had different degrees ($d(u) < d(v)$), we could replace $u$'s neighborhood with $v$'s neighborhood (cloning $v$). This transformation preserves $K_{r+1}$-freeness and strictly increases the total edge count, contradicting maximality. Hence, nonadjacent vertices in $G$ must have equal degrees.

If two nonadjacent equal-degree vertices $u, v$ had different neighborhoods, cloning $u \to v$ or $v \to u$ leaves total edge count unchanged, but at least one direction strictly increases $\sum_v d(v)^2$, contradicting our choice of $G$. Thus, nonadjacency in $G$ is an equivalence relation: $G$ is a complete $k$-partite graph. To avoid $K_{r+1}$, $G$ can have at most $r$ parts, and balancing part sizes maximizes edges, proving $e(G) \le t_r(n)$.

Solved Example. Forbidding $K_4$ on eight vertices ($n=8, r=3$), the balanced part sizes are $3, 3, 2$. The exact extremal number is:

Exercise. Compute $\operatorname{ex}(10,K_4)$. Hint: Partition 10 vertices into 3 parts of sizes $4, 3, 3$. Solution: $e(T_3(10)) = (4 \times 3) + (4 \times 3) + (3 \times 3) = 12 + 12 + 9 = 33$.

19.2 Mantel's theorem and complete multipartite graphs

What & Fundamentals. Mantel's theorem (1907) is the foundational special case of Turán's theorem for $r=2$ (forbidding triangles $K_3$). Beyond being a simple corollary, Mantel's original degree-sum proof establishes a powerful local-to-global counting technique.

Mantel's Theorem. Every triangle-free graph $G$ on $n$ vertices satisfies:

The upper bound is achieved uniquely by the complete balanced bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$.

Proof using Degree Cauchy–Schwarz. Let $uv \in E(G)$. If $u$ and $v$ shared a common neighbor $w \in N(u) \cap N(v)$, then $\{u, v, w\}$ would form a triangle $K_3$. Thus, for every edge $uv$, $N(u)$ and $N(v)$ are disjoint, giving $d(u) + d(v) \le n$. Summing over all $m$ edges:

By Cauchy–Schwarz inequality and the Handshaking Lemma ($\sum d(v) = 2m$):

Combining the two inequalities gives $\frac{4m^2}{n} \le nm \implies m \le \frac{n^2}{4}$. Since $m$ is an integer, $m \le \lfloor n^2 / 4 \rfloor$.

Exercise. Which split gives the most edges on seven vertices: $1+6$, $2+5$, or $3+4$? Hint: Multiply the part sizes. Solution: Products are $6, 10, 12$. The maximum is $K_{3,4}$ with $\lfloor 49/4 \rfloor = 12$ edges.

19.3 Erdős–Stone–Simonovits theorem

What & Concept. Turán's theorem determines the exact maximum density for forbidden complete graphs $K_{r+1}$. What happens when the forbidden subgraph $H$ is arbitrary (such as a cycle $C_5$, a wheel, or a non-complete graph)?

The Erdős–Stone–Simonovits Theorem reveals a fundamental principle: the asymptotic density threshold for forbidding any graph $H$ is dictated solely by its chromatic number $\chi(H)$ (the minimum number of colors required to properly color $H$).

Erdős–Stone–Simonovits Theorem (1946 / 1966). For every fixed graph $H$ with chromatic number $\chi(H) = r+1 \ge 2$:

Here $o(1) \to 0$ as $n \to \infty$. This result demonstrates that non-clique subgraphs behave asymptotically like complete $K_{r+1}$ cliques of the same chromatic number!

Why Chromatic Number Controls Density:

1. Lower Bound: The Turán graph $T_r(n)$ is $r$-colorable by definition. Since $\chi(H) = r+1$, $H$ cannot be properly colored with $r$ colors, so $T_r(n)$ can never contain $H$ as a subgraph. Thus $\operatorname{ex}(n, H) \ge e(T_r(n)) = \left(1 - \frac{1}{r}\right) \frac{n^2}{2}$.
2. Upper Bound (Erdős–Stone Embedding): If a graph $G$ has edge density strictly exceeding $1 - \frac{1}{r} + \varepsilon$, then for sufficiently large $n$, $G$ must contain a huge complete $(r+1)$-partite graph $K_{t, t, \ldots, t}$. By choosing part size $t \ge |V(H)|$, we can embed $H$ into $K_{t, t, \ldots, t}$ by mapping each color class of $H$ into a distinct part.

Solved Example. The 5-cycle $C_5$ has chromatic number $\chi(C_5) = 3$ (odd cycles require 3 colors). Here $r+1 = 3 \implies r = 2$. Therefore:

Exercise. What leading term does the theorem give when $\chi(H)=4$? Hint: $r=3$. Solution: $\operatorname{ex}(n,H) = \left(1 - \frac{1}{3}\right) \frac{n^2}{2} + o(n^2) = \frac{n^2}{3} + o(n^2)$.

19.4 Forbidden subgraphs and Zarankiewicz problems

What & Definitions. When $\chi(H) = 2$ (bipartite graphs such as trees, even cycles $C_4, C_6$, or $K_{s,t}$), the Erdős–Stone–Simonovits theorem yields $\operatorname{ex}(n, H) = o(n^2)$. The leading quadratic density drops to zero, and the problem shifts to determining sub-quadratic growth rates ($O(n^{2-\alpha})$).

The Zarankiewicz Problem asks: What is the maximum number of edges in a bipartite graph $G = (X, Y, E)$ with part sizes $|X|=p, |Y|=q$ that contains no complete bipartite subgraph $K_{s,t}$ with $s$ vertices in $X$ and $t$ vertices in $Y$? This maximum edge count is denoted $z(p, q; s, t)$.

Equivalently, in terms of a $p \times q$ binary incidence matrix $M$, $z(p,q; s,t)$ is the maximum number of 1-entries in $M$ such that no $s \times t$ submatrix consists entirely of 1s.

Solved Example (6-Cycle Matrix). The $3 \times 3$ matrix above contains 6 ones. Every pair of rows shares exactly one 1-column, avoiding any $2 \times 2$ all-ones submatrix. In graph terms, this represents $C_6$, which is $K_{2,2}$-free ($K_{2,2}$ is a 4-cycle). Adding a single 1-entry immediately creates a $2 \times 2$ all-ones block, confirming that 6 is the absolute maximum: $z(3,3;2,2) = 6$.

Exercise. Can a bipartite graph on fixed parts of sizes $p, q$ have more than $pq$ edges? Hint: Count possible cross-part pairs. Solution: No, because a simple bipartite graph contains only cross-edges between $X$ and $Y$, limiting maximum edges to $|X||Y| = pq$.

19.5 Extremal bipartite graphs and the Kővári–Sós–Turán theorem

What & Fundamentals. The Kővári–Sós–Turán (KST) Theorem (1954) establishes a rigorous upper bound on the Zarankiewicz number and the extremal number $\operatorname{ex}(n, K_{s,t})$ by double-counting star subgraphs $K_{1,s}$.

KST Theorem (Rectangular Form). Suppose $s \ge 2, t \ge 2$. If a bipartite graph $G = (X, Y, E)$ with $|X|=p, |Y|=q$ contains no $K_{s,t}$ with $s$ vertices in $X$, then its edge count $e(G)$ satisfies:

For a general $n$-vertex graph, applying a probabilistic random bipartite cut yields the general extremal bound:

Proof via Star Double-Counting. Count pairs $(y, S)$ where $y \in Y$ and $S \subseteq X$ is an $s$-element subset of neighbors of $y$. On one hand, each vertex $y \in Y$ contributes $\binom{d(y)}{s}$ such pairs. On the other hand, no $s$-element subset $S \subseteq X$ can share $t$ or more common neighbors in $Y$ (which would form $K_{s,t}$). Thus, each of the $\binom{p}{s}$ subsets in $X$ has at most $t-1$ common neighbors:

Applying Jensen's inequality to the convex function $f(x) = \binom{x}{s}$ gives $q \binom{e/q}{s} \le (t-1) \binom{p}{s}$. Solving for $e$ yields $e(G) = O(p q^{1-1/s})$.

Sharper Formula for $K_{2,2}$ ($s=2, t=2$):

Exercise. Bound the edge count of a $K_{2,2}$-free bipartite graph with $p=4, q=4$. Hint: Substitute into the $K_{2,2}$ formula. Solution: $e \le \frac{4 + \sqrt{16 + 4(4)(12)}}{2} = \frac{4 + \sqrt{208}}{2} \approx \frac{4 + 14.42}{2} = 9.21 \implies e \le 9$.

19.6 Stability theorems

What & Fundamentals. Knowing that $\operatorname{ex}(n, K_{r+1}) = t_r(n)$ is attained by $T_r(n)$ answers the density question. Stability theory (pioneered by Erdős and Simonovits) answers the structural question: If a $K_{r+1}$-free graph $G$ has edge count $e(G) \ge t_r(n) - \delta n^2$ (close to optimal), must $G$ be structurally close to the Turán graph $T_r(n)$?

Erdős–Simonovits Stability Theorem. Fix $r \ge 2$. For every $\eta > 0$, there exist $\delta > 0$ and $n_0$ such that if $n \ge n_0$, $G$ is $K_{r+1}$-free, and $e(G) \ge t_r(n) - \delta n^2$, then $G$ can be transformed into the Turán graph $T_r(n)$ by modifying (adding or deleting) at most $\eta n^2$ edges.

Explicit Triangle-Free Edit Bound. Let $G$ be triangle-free with $m = e(G)$ and density deficit $D = n^2/4 - m$. Pick a vertex $v$ of maximum degree $\Delta$. Set $A = N(v)$ and $B = V(G) \setminus A$. Because $G$ is triangle-free, $A$ is an independent set. The number of internal edges within $B$ satisfies $e(B) \le D$. Deleting at most $D$ internal edges makes $G$ bipartite. Adding missing cross-edges between $A$ and $B$ costs at most $2D$ edits. Total edits to make $G$ complete bipartite is at most $3D$.

Exercise. For a 5-cycle $C_5$, pick vertex $v$, set $A = N(v)$ ($|A|=2$), and $B = V(C_5) \setminus A$ ($|B|=3$). How many internal edges lie in $B$? Hint: Check connections among the 3 vertices in $B$. Solution: Exactly 1 internal edge lies in $B$. Deleting it leaves $C_5$ bipartite ($K_{2,3}$).

19.7 Szemerédi's regularity lemma

What & Concept. Szemerédi's Regularity Lemma (1978) is one of the most powerful tools in modern combinatorics. It asserts that every large dense graph can be partitioned into a bounded number of equal-sized clusters such that the edges between almost all pairs of clusters behave almost like purely random bipartite graphs.

Definition ($\varepsilon$-Regular Pair). For disjoint vertex sets $A, B$, their edge density is $d(A,B) = \frac{e(A,B)}{|A||B|}$. A pair $(A,B)$ is $\varepsilon$-regular if for all subsets $A' \subseteq A$ and $B' \subseteq B$ satisfying $|A'| \ge \varepsilon |A|$ and $|B'| \ge \varepsilon |B|$, the density condition holds:

Szemerédi's Regularity Lemma. For every $\varepsilon > 0$ and integer $m_0 \ge 1$, there exist integers $M, n_0$ such that every graph with $n \ge n_0$ vertices has an equitable partition $V = V_0 \cup V_1 \cup \cdots \cup V_k$ such that $m_0 \le k \le M$, $|V_1| = |V_2| = \cdots = |V_k|$, $|V_0| \le \varepsilon n$, and all but at most $\varepsilon k^2$ pairs $(V_i, V_j)$ are $\varepsilon$-regular.

Exercise. Is an empty bipartite pair (zero edges between $A$ and $B$) $\varepsilon$-regular? Hint: Check subset densities. Solution: Yes, because $d(A',B') = d(A,B) = 0$ for all subsets, so $|0 - 0| \le \varepsilon$ holds trivially.

19.8 Graph counting and removal lemmas

What & Concept. Combining Szemerédi's regularity partitions with Counting Lemmas establishes that if cluster pairs $(A,B), (B,C), (A,C)$ are $\varepsilon$-regular with densities $d_{AB}, d_{BC}, d_{AC} \ge d$, then the number of triangles spanning $A, B, C$ closely mirrors the expectation in a random graph!

Triangle Counting Lemma. Let $A, B, C$ be disjoint vertex sets where all three pairs are $\varepsilon$-regular with densities $\ge d \ge 2\varepsilon$. The number of triangles with one vertex in each set is at least:

Triangle Removal Lemma (Ruzsa–Szemerédi, 1978). For every $\eta > 0$, there exists $\beta > 0$ such that any graph on $n$ vertices with at most $\beta n^3$ triangles can be made completely triangle-free by removing at most $\eta n^2$ edges.

Exercise. A graph consists of $t$ disjoint triangles ($n = 3t$). How many edge deletions are necessary and sufficient to make it triangle-free? Hint: Each triangle requires removing at least 1 edge. Solution: Exactly $t = n/3$ edge deletions (removing 1 edge per triangle).

19.9 Dependent random choice

What & Concept. Dependent Random Choice (DRC) is a powerful probabilistic technique used to find large subsets of vertices whose small subsets all share many common neighbors. Instead of choosing vertices uniformly at random, DRC picks a small set of vertices $T$ at random and defines $U$ as their joint neighborhood. Vertices with high degree are much more likely to land in $U$.

DRC Guiding Formula. In a bipartite graph $G = (X, Y, E)$ with $|X|=p, |Y|=q$ and average edge density $\alpha = \frac{e(G)}{pq}$, DRC guarantees the existence of a subset $W \subseteq X$ of size:

such that every $r$-element subset of $W$ shares at least $b$ common neighbors in $Y$.

Solved Example. Let $p=q=8, \alpha \ge 3/4, t=r=2, b=2$. Substituting into the DRC bound gives:

Since $|W|$ is an integer, $|W| \ge 3$. Thus, $X$ contains a 3-element set $W$ where every pair shares at least 2 common neighbors in $Y$, guaranteeing a $K_{2,2}$ copy!

Exercise. Repeat the DRC calculation for $p=q=8, \alpha \ge 1/2, t=r=2, b=2$. Hint: First term becomes $8(1/4) = 2$. Solution: $|W| \ge 2 - 28(1/16) = 2 - 1.75 = 0.25 \implies |W| \ge 1$. A 1-element set is vacuous for pairs ($r=2$), so these parameters do not guarantee $K_{2,2}$.

19.10 Spectral extremal graph theory

Optional extension. Sections 31.1 and 31.3 provide recommended matrix and spectral background, but this chapter's elementary edge bounds do not depend on them. The bridge here uses the adjacency matrix and a variational description of its largest eigenvalue. Nikiforov's survey supplies a full advanced follow-up on spectral extremal methods.

The adjacency matrix $A_G$ has entry 1 when two vertices are adjacent and 0 otherwise. It is symmetric, so its eigenvalues are real. For a graph, its spectral radius $\lambda(G)$ equals its largest eigenvalue, and

One may choose a maximizing vector with nonnegative entries: replacing each entry by its absolute value cannot decrease the numerator. Taking the all-ones vector gives $\lambda(G)\ge2m/n$. The maximum-degree bound $\lambda(G)\le\Delta(G)$ follows by applying an eigenvector equation at a largest entry of a nonnegative eigenvector. Regular graphs achieve both bounds with their common degree.

For $K_{a,b}$, its positive eigenvector can be constant on each part. If those constants are $u,v$, then $\lambda u=bv$ and $\lambda v=au$, so

Thus among complete bipartite graphs on a fixed number of vertices, balance maximizes both edges and spectral radius.

A spectral Mantel inequality. If $G$ is triangle-free, then

Together with $2m/n\le\lambda(G)$, this recovers Mantel: for $m\gt0$, $4m^2/n^2\le m$, hence $m\le n^2/4$. The stronger eigenvalue statement deserves its own proof rather than being inferred from the edge bound.

Weighted clique lemma. If $G$ has no clique larger than $r$ and $y_v\ge0$ with $\sum_v y_v=1$, then

To prove it, take a maximizing weight assignment with the smallest possible positive support. If two supported vertices are nonadjacent, their combined mass can be placed entirely on whichever has the larger weighted neighborhood, without decreasing the objective. This contradicts minimal support. Hence the support is a clique of size $s\le r$. On a clique, the objective is $(1-\sum_v y_v^2)/2\le(1-1/s)/2$, by Cauchy–Schwarz. This establishes the bound.

Proof of spectral Mantel. For a nonnegative eigenvector $x$ with $\sum_v x_v^2=1$, Cauchy–Schwarz over the edges gives

Apply the weighted clique lemma with $r=2$ and $y_v=x_v^2$; the last sum is at most $1/4$. Therefore $\lambda(G)\le\sqrt m$. The graph with no edges has spectral radius zero and also satisfies the statement.

Solved comparison on six vertices. The star $K_{1,5}$ and $C_5$ plus an isolated vertex both have five edges and are triangle-free. Their spectral radii are respectively $\sqrt5$ and 2. The same edge count need not give the same spectral radius: concentration of degrees changes the eigenvalue. The extremal construction $K_{3,3}$ has nine edges and spectral radius 3, attaining $\lambda^2=m$.

The weighted lemma also proves the general bound $\lambda(G)\le(1-1/r)n$ for $K_{r+1}$-free graphs: normalize a nonnegative eigenvector by its sum, apply the lemma, and use $(\sum_v x_v)^2\le n\sum_v x_v^2$. This is sharp for $T_r(n)$ when $r$ divides $n$. The exact spectral Turán theorem states $\lambda(G)\le\lambda(T_r(n))$ for every $n$; the displayed continuous bound alone does not prove the sharper unbalanced case.

Exercise. Find the spectral radius of $K_{2,4}$ and compare it with that of $K_{3,3}$. Hint: use $\sqrt{ab}$. Solution: $\sqrt8\lt3$, matching the improvement from eight to nine edges when the parts are balanced.

Identify an extremal construction and prove a matching upper bound

The investigation asks you to solve one exact extremal problem in three languages: a graph construction, a degree proof, and a spectral bound. Every graph considered has the fixed labeled vertex set $\{1,2,3,4,5,6\}$.

Application: incidence networks. In a network linking users to resources, a $K_{2,2}$ means two users share two resources. A system that allows any pair of users to share at most one resource is therefore modeled by a $K_{2,2}$-free incidence graph. KST bounds how many assignments are possible under this specific restriction. This is a capacity bound, not a guarantee of security or reliability without additional domain assumptions.

For a different cross-disciplinary connection, the linear iteration $x_{t+1}=\gamma A_Gx_t$ models a simple process passing influence along edges. Its growth scale is governed by $\gamma\lambda(G)$: an eigenvector of the largest eigenvalue is multiplied by that factor at each step. Thus the comparison of two equal-edge graphs with different spectral radii has a concrete dynamical meaning. Under triangle-freeness, the spectral inequality constrains this amplification as well as the edge count. The model is linear; applying it to a real process requires checking whether that assumption is appropriate.

The central habit is to pair a construction with a proof and to name the optimized quantity. Exact edge maxima, asymptotic densities, edit distances, pattern counts, and spectral radii answer related but distinct questions.