Turán 图

完全 $r$ 部图把所有缺边都藏在各部内部。若总顶点数固定，边数等于总点对数减去各部内部点对数。平方和在部大小尽量均衡时最小，所以缺边最少、跨部边最多。这是一条离散均衡原则：若两部大小分别为 $a$ 与 $b$ 且 $a\ge b+2$，把一个顶点从大部移到小部，会使平方和下降并让边数增加 $a-b-1$。

图的密度来自部之间的彻底连接，避开大团则来自部内的彻底空缺。两个要求在同一划分上同时实现，因而 Turán 图成为许多极值问题的基准构造。重要的是“完全多部”与“均衡”缺一不可：前者保证给定划分下没有遗漏可加的跨部边，后者保证不同划分之间边数最优。

$T_3(8)$ 的部大小为 $3,3,2$。跨部边数可逐项核算为

也可从全部 $(\genfrac{}{}{0ex}{}{8}{2})=28$ 个点对中减去部内的 $(\genfrac{}{}{0ex}{}{3}{2})+(\genfrac{}{}{0ex}{}{3}{2})+(\genfrac{}{}{0ex}{}{2}{2})=7$ 对。它含许多三角形：各从三部取一点即可；但不含 $K_4$，因为四个顶点必有两个落入同一部。

不均衡的完全三部图 $K_{4,2,2}$ 只有 $4\cdot 2+4\cdot 2+2\cdot 2=20$ 条边。把大部的一个顶点移到任一小部，得到 $3,3,2$，正好多出一条边。这是均衡交换论证的最小可见轨迹，而不是仅靠连续函数猜测“平均最好”。

边界参数也要说清。$T_1(n)$ 是空图；当 $r\ge n$ 时，每个非空部都只有一个顶点，故 $T_r(n)=K_n$。下标 $r$ 表示部数而非正则度数；当 $r\nmid n$ 时，图甚至不正则，位于大小为 $q$ 与 $q+1$ 的部中的顶点度数分别为 $n-q$ 与 $n-q-1$。它也不是任意完全 $r$ 部图的别名，部大小失衡时应写明具体的 $K_{n_1,\dots ,n_r}$。

Turán 定理理路Turán 定理Turán's theorem · 图兰定理不含给定大团的有限简单图以均衡完全多部图为同构意义下唯一的最多边构造。断言 $T_r(n)$ 是 $n$ 点 $K_{r+1}$-free 图中边数唯一最大的构造。Erdős–Stone 定理理路Erdős–Stone 定理Erdős–Stone theorem · Erdős–Stone–Simonovits theorem · 厄多斯–斯通定理固定禁图的色数决定其极值数的二次主项，而不决定低阶误差与精确取等结构。进一步说明，只要固定禁图的色数为 $r+1$，它的极值数二次主项仍由 $t_r(n)$ 控制；低阶项和精确取等者则可能依赖禁图的细节。

在稳定性方法理路极值组合学中的稳定性方法Stability method in extremal combinatorics · Erdős–Simonovits stability · 极值稳定性方法从目标值的微小亏损推出可行对象在编辑距离上接近极值构造的结构化方法。中，$T_r(n)$ 还充当几何模板：一个 $K_{r+1}$-free 图若边数只比 $t_r(n)$ 少 $o(n^2)$，就能通过改动 $o(n^2)$ 条边变成某个 $r$ 部 Turán 图。该结论比边数上界强，却仍只保证编辑距离小，不保证逐点度数或同构。