Erdős–Stone 定理

色数把 $H$ 的顶点压缩成 $r+1$ 个独立颜色类。若宿主图的密度固定超过 $r$ 部 Turán 密度，密集连接便不仅迫使一个 $K_{r+1}$，还迫使各顶点被复制多次的完全多部结构；当每部足够大时，它容得下 $H$ 的各颜色类。禁图内部有多少边、颜色类是否均衡，只影响需要多大的复制和低阶误差，不影响二次主项。

下界方向极其具体：Turán 图理路Turán 图Turán graph · T_r(n) · 图兰图把顶点尽量均匀分成若干部并连接全部跨部顶点所得的完全多部图。 $T_r(n)$ 是 $r$ 部图，任何子图也至多需要 $r$ 色，所以它不可能含 $\chi (H)=r+1$ 的 $H$。故

上界方向才是定理的核心。若只需嵌入固定的 $H$，一条标准证明路线借Szemerédi 正则性引理理路Szemerédi 正则性引理Szemerédi regularity lemma · Graph regularity lemma · 塞梅雷迪正则性引理任意充分大的稠密图都能分成有界多个等大顶点簇，使绝大多数簇对在大子集尺度上呈现近似均匀密度。把图压缩成有限约化图，在约化图中用Turán 定理理路Turán 定理Turán's theorem · 图兰定理不含给定大团的有限简单图以均衡完全多部图为同构意义下唯一的最多边构造。找到团，再以计数引理理路图计数引理Graph counting lemma · Counting lemma for regular pairs · 正则对计数引理固定小图的各条边落在正则簇对上时，其跨簇副本密度与边密度乘积之间的加性误差由正则参数控制。提升出足以容纳 $H$ 的固定大小 blow-up。前述 $t=\mathrm{\Theta }(\log n)$ 的结构版还需要更细的放大论证；基础计数引理本身只对预先固定的目标图给出统一控制。

五圈 $C_5$ 的色数为 $3$，所以

下界由完全二分图给出，因为二分图不含奇圈。定理却没有声称对每个 $n$ 都有 $\mathrm{ex}(n,C_5)=\lfloor n^2/4\rfloor$，也没有仅凭色数刻画全部取等图；这些属于更精确的问题。

若 $H$ 是二分图，则 $\chi (H)=2$、$r=1$，公式只给

它不能分辨 $K_{2,2}$ 的 $n^{3/2}$ 尺度、树的线性尺度或不同偶圈的幂次。此时需转向Zarankiewicz 型问题理路Zarankiewicz 问题Zarankiewicz problem · Zarankiewicz function · z(m,n;s,t)在固定尺寸的零一矩阵中排除全一子矩阵，等价地求定向禁止完全二分子图时的最大边数。、偶圈方法或依赖随机选择。若 $H$ 没有边，则 $\chi (H)=1$，上述分母无意义；“至少含一条边”不是装饰性条件。

定理固定 $H$ 后令 $n\to \mathrm{\infty }$。若禁图 $H=H_n$ 随 $n$ 增长，嵌入所需的部大小也增长，$o(1)$ 不能保持统一。类似地，结构版中 $t$ 只有对数阶，不能误写成固定正比例的 $n$。

该定理把稠密图的普通禁子图极值问题按色数理路色数Chromatic number一张图存在正常顶点染色所需的最少颜色数。分成两类：色数至少三时，主项是正的二次密度；二分禁图时，密度极限为零，次二次阶成为真正信息。它也说明具有相同色数的禁图共享主项，却可能拥有完全不同的误差项。

Erdős–Simonovits 稳定性理路极值组合学中的稳定性方法Stability method in extremal combinatorics · Erdős–Simonovits stability · 极值稳定性方法从目标值的微小亏损推出可行对象在编辑距离上接近极值构造的结构化方法。进一步表明，$H$-free 图若接近这个主项，就在编辑距离上接近 $T_r(n)$。超饱和定理理路极值图中的超饱和Supersaturation in extremal graphs · Erdős–Simonovits supersaturation theorem · 超饱和定理图的边密度固定超过禁图极值密度时，禁图副本数必从一个跃升到顶点数的正确幂次量级。则说明密度固定超过主项后会出现 $\mathrm{\Theta }(n^{v(H)})$ 量级的 $H$ 副本。三者依次给出阈值、近阈值结构与越阈值计数。