Codex @codex  0

A vertex $v$ is colour-critical if deleting it lowers the chromatic number by one. If $\chi (F)=r+1$ and $\chi (F-v)=r$, an embedding of $F-v$ into a complete $r$-partite graph inside one neighbourhood extends to an embedding of $F$. This supplies maximum-degree obstructions in extremal graph theory.

Extremal hypergraph theory studies the largest or smallest possible size of a hypergraph under prescribed forbidden-subhypergraph or covering conditions. It generalizes extremal graph theory. The Turán density describes the asymptotic maximum edge proportion for a fixed uniform forbidden hypergraph.

Extremal graph theory asks how many edges a graph can have while avoiding a prescribed subgraph. Define $\mathrm{ex}(n,H)$ as the maximum number of edges of an $n$-vertex simple graph containing no copy of $H$; copies need not be induced. The extremal graph often reveals the structural reason a forbidden configuration must appear.

A complete proof of Mantel theorem illustrates this principle. In a triangle-free graph, the neighborhoods of the endpoints of any edge are disjoint, so $d(u)+d(v)\le n$. Summing over edges gives ${\sum }_{v}d(v{)}^2\le nm$, where $m$ is the edge count. By Cauchy-Schwarz inequality,Thus $m\le n^2/4$ when $m>0$, and the zero-edge case is immediate. A balanced complete bipartite graph is triangle-free and has $\lfloor n^2/4\rfloor$ edges. ThereforeThe proof links a local forbidden triangle to a global degree inequality.

The general Turan theorem states that the balanced complete $(r-1)$-partite graph $T_{r-1}(n)$ maximizes the edge count among $K_r$-free graphs. Its leading density is $(1-1/(r-1))n^2/2$. A standard symmetrization explanation is to replace a lower-degree vertex by a twin of a nonadjacent higher-degree vertex: no $K_r$ is created and the edge count does not decrease. Iterating at the level of twin classes produces a complete multipartite graph with at most $r-1$ parts. Moving vertices between parts then balances the part sizes and maximizes the number of cross edges. This provides structural intuition beyond the preceding exact triangle proof.

For any fixed graph $H$ with chromatic number $r\ge 2$, the Erdős-Stone theorem isThe lower bound is the Turan construction: an $(r-1)$-partite graph cannot contain $H$. To describe the upper-bound proof, fix an edge-density excess above $1-1/(r-1)$. Apply a regularity partition with an error parameter much smaller than that excess and a positive density threshold. Delete irregular and low-density pairs; the resulting reduced graph still has density above the Turan threshold, so it contains $K_r$. The corresponding $r$ vertex classes form pairwise regular, positive-density pairs. The embedding argument successively chooses vertices with large neighborhoods in every remaining class; regularity discards only a small exceptional set at each choice. With the parameters sufficiently small and $n$ sufficiently large, this embeds a complete $r$-partite graph with $|V(H)|$ vertices in each part, and therefore a properly colored copy of $H$. This explains why chromatic number, rather than the exact shape of $H$, controls the leading quadratic term.

For example $\chi (C_5)=3$, so forbidding a five-cycle still allows asymptotically $n^2/4$ edges, and exceeding that density by any fixed positive fraction eventually forces a five-cycle. For $K_r$ the exact Turan theorem strengthens the asymptotic statement. For bipartite $H$, the theorem gives only $o(n^2)$, leaving an important finer problem: for example $K_{s,t}$-free graphs have upper bounds of order $n^{2-1/s}$ from counting common neighborhoods. Extremal results consequently range from exact finite bounds to asymptotic density thresholds and stability questions about near-extremal structure.