Turán 定理

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

对称化同时证明上界与取等唯一性 ​

固定 $n,r$，在有限个 $K_{r+1}$-free 图中选任意一幅边数最大的 $G$。若不相邻顶点 $u,v$ 满足 $d(u)<d(v)$，把 $u$ 的邻域改成 $v$ 的邻域，便严格增加边数。新图仍禁 $K_{r+1}$：新团若用到 $u$，用 $v$ 替换就得到旧团；它不可能同时用到这两个不相邻的点。因此极值图中任意两个不相邻顶点度数相等。

还须证明原图已经是完全多部图。若有三个不同顶点 $u,v,w$，其中 $uv,vw$ 不是边而 $uw$ 是边，则三者度数同为 $d$。删去 $u,w$，再加入两个互不相邻的 $v$ 的孪生点。删去的边数是 $2d-1$，因为 $uw$ 被两次度数计费；新增边数是 $2d$，因为 $v$ 原来不邻接这两个点。新图仍禁 $K_{r+1}$，却恰好多一条边，矛盾。

所以“相同或不相邻”是顶点上的等价关系：每一类内部无边，不同类之间全部相连。$G$ 是完全多部图，非空部至多 $r$ 个。若部数少于 $min\{r,n\}$，拆开一个至少含两点的部便可增加边数而仍禁团；若两部大小相差至少二，移一个顶点到较小部也会增加边数。因此任意极值图都恰为均衡的 $T_r(n)$，既给出边数上界，也证明同构意义下的唯一性。$n=0$ 时只有空图，直接成立。

取 $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 极值图。定理比较所有可行图的边数，而不是只检查局部不可加边性。

由定理可立刻推出：边数超过 $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$ 的稀疏图未必含大团。