= Minimum degree of an extremal forbidden-subgraph graph
If a fixed <graph> $F$ has <chromatic number> $r+1$, every extremal $F$-free <graph> $G$ on $n$ <vertices> has <minimum degree of a graph> $(1-1/r+o(1))n$. Use a <high-minimum-degree multipartite stability subgraph> $H$: replacing any <vertex> by one adjacent to all but one class of $H$ preserves $F$-freeness. Any supposed new copy of $F$ can replace the new <vertex> by an unused <common neighbour> in the omitted class. Extremality therefore gives the lower bound on every <degree of a vertex>; the <Erdős-Stone theorem> gives the upper bound on the average <degree of a vertex>.
Back to article page
