Turán 定理

要避开 $K_{r+1}$，最经济的办法不是零散删边，而是把所有缺边集中到 $r$ 个独立部内，再把部间边全部保留。集中缺边制造了稳定的“不能同部取两点”证书；均衡各部则让必须删除的部内点对总数最少。

Zykov 对称化把这幅图像变成证明。若两个不相邻顶点的邻域不同，就把度较小者替换成度较大者的“孪生点”：删去它原有边，并令它邻接后者的全部邻点。边数不减，且若新图出现 $K_{r+1}$，用被复制的原顶点替换孪生点便会在旧图中得到同样的团，矛盾。配合一个在同度时严格改进的有限势函数反复进行，最终所有不相邻关系分成孪生类，图成为完全多部图；禁团条件把非空部数限制在 $r$ 以内。最后用部大小交换完成均衡化。

等号唯一性来自两次“不损失”都必须取等：终态不能遗漏任何跨部边，并且必须使用 $min\{r,n\}$ 个非空部；否则还可把一个至少含两点的部拆开而严格增边。任意两部大小相差至少二也会因移动一个顶点而严格增边。因此取等图不能只是“看起来接近分部”，而必须同构于精确均衡的 $T_r(n)$。

取 $r=2,n=7$。定理给出

$K_{3,4}$ 有 $12$ 条边且无三角形，所以界可达；等号唯一性又说明任何七点十二边无三角形图都同构于它。相比之下，星图 $K_{1,6}$ 有 $6$ 条边，七圈 $C_7$ 有 $7$ 条边；两者虽都无三角形，却远未达到极值。

条件排除的是子图而不是诱导子图。若只禁止诱导 $K_{r+1}$，任何更大的完全图都含诱导 $K_{r+1}$，此例看不出差别；但把禁图换成非完全图后，两种问题会分离。结论也不允许把 $K_{r+1}$ 换成任意色数为 $r+1$ 的 $H$ 后仍声称精确值是 $t_r(n)$：普遍成立的只是渐近主项，低阶误差与唯一取等需要额外假设。

另一个边界是“最大”与“饱和”。一个 $K_{r+1}$-free 图可能再加任意缺边都会生成 $K_{r+1}$，却仍比 $t_r(n)$ 稀疏；这种图是饱和图，不必是 Turán 极值图。定理比较所有可行图的边数，而不是只检查局部不可加边性。

由平均度 $2e(G)/n$ 可立刻推出：边数超过 $t_r(n)$ 时必含 $K_{r+1}$。超饱和定理公理库极值图中的超饱和Supersaturation in extremal graphs · Erdős–Simonovits supersaturation theorem · 超饱和定理图的边密度固定超过禁图极值密度时，禁图副本数必从一个跃升到顶点数的正确幂次量级。把“至少一个”加强为“超过固定密度就有正比例的许多副本”；稳定性方法公理库极值组合学中的稳定性方法Stability method in extremal combinatorics · Erdős–Simonovits stability · 极值稳定性方法从目标值的微小亏损推出可行对象在编辑距离上接近极值构造的结构化方法。则把接近取等的图逼近 Turán 构造。

Erdős–Stone 定理公理库Erdős–Stone 定理Erdős–Stone theorem · Erdős–Stone–Simonovits theorem · 厄多斯–斯通定理固定禁图的色数决定其极值数的二次主项，而不决定低阶误差与精确取等结构。以 Turán 定理提供的下界构造为起点，证明任意固定 $H$ 的非二分情形都由 $\chi (H)$ 决定二次主项。Turán 定理也给图着色提供密度证书：一个图若边数大于 $t_r(n)$，不仅不能是 $r$ 部图，而且必然已经出现一个 $K_{r+1}$；反向不成立，色数超过 $r$ 的稀疏图未必含大团。