图兰定理

图兰定理是一个图论中的定理，关于 K_r+1 免除图的边数。简而言之，在所有 n 点且不包(r+1)-点团的图中，边数最多的图是图兰图，而且只有图兰图达到边数的最大值。图兰图是将 n 点分成大小差不多的r 部分，两点再向一部份若且惟若两点之间有连边。

图兰定理于1941年首次由匈牙利数学家图兰·帕尔（Turán Pál）发现，但 r=2 的情形早在 1907 年由 Mantel 提出。

叙述

若 G 是一个有 n 点的图，而且完全图 K_r+1 不是 G 的子图，则 G 最多有${\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}=\left(1-{\frac {1}{r}}\right)\cdot {\frac {n^{2}}{2}}$条边。此外，如果 G 有$\left(1-{\frac {1}{r}}\right)\cdot {\frac {n^{2}}{2}}$条边，则 G 一定是图兰图 $T_{n,r}$。

图兰图

定义

图兰图 $T_{n,r}$ 的定义为一个特殊的具有 n 点的完全r-分图，其中各部份的顶点数的差不超过1，或者说，r 个部份分别有$\left\lfloor {\frac {n}{r}}\right\rfloor ,\left\lfloor {\frac {n+1}{r}}\right\rfloor ,\dots ,\left\lfloor {\frac {n+r-1}{r}}\right\rfloor$个顶点。

性质

在所有具有 n 点的 r-分图中，图兰图 $T_{n,r}$是唯一一个边数最多的图。

证明

假设 K 是一个边数最多的 r-分图，那么很明显的，K 是一个完全 r-分图。

假设 K 的 r 个部份的点集中，有 U、V 两部分满足 $|U|\geq |V|+2$，定义 K' 为取出 K 中 U 的一个点 x，移动到 V 之中，并且删除所有原本 x 与 V 中的点的连边，然后将 x 与所有 U 中的点连边，于是，K' 仍然是一个完全 r-分图，且经过此操作，有 $|E(K')|=|E(K)|+(|U|-1)-|V|\geq |E(K)|+1$。因此，K' 比 K 有更多的边，产生矛盾。因此，r-分图 K 的各部分点集的顶点数至多差 1，即 K 是图兰图 $T_{n,r}$。

定理证明

对于 r 做数学归纳法，当 r=0，不存在 K₂ 子图，即没有边，因此 G 一定是“完全一分图”，G 的顶点集形成一个独立集。

对一般的正整数 r，若 G 是一个有 n 点的图，而且完全图 K_r+1 不是 G 的子图，则考虑 G 中度数最大的点 x，设 $N(x)$为 x 的所有邻居所形成的集合，设 G' 为$N(x)$的导出子图，因此 K_r 不是 G' 的子图，否则该 K_r 加上点 x 是 G 的一个 K_r+1 子图。

由归纳法假设，G' 的边数不超过图兰图$H':=T_{|G'|,r-1}$的边数，定义 H 是一个完全 r-分图，包含 H' 和另外 |G|-|G'| 个点，这些点互相不相邻，并和所有 H' 中的点相邻。于是有

$|E(G)|\leq \sum _{v\in V(G)-V(G')}\deg _{G}(v)+|E(G')|\leq (|G|-|G'|)\deg _{G}(x)+|E(G)|=|E(H')|\leq |E(T_{n,r})|$

其中，第一个不等号成立是因为其右边将两端点都在 V(G)-V(G') 的边算了两次，其馀的边算了一次。故图兰图是所有满足条件的图中边数最多的之一。

最后，当等式成立时，G 在 V(G)-V(G') 中没有边，且 G' 与图兰图 H' 有一样多的边，尤归纳法假设知道，G' 同构于 H'。因此 G 是一个 r-分图，V(G)-V(G') 是其中的一部分。由于图兰图是多分图中唯一边数最多的，因此 G 是图兰图 $T_{n,r}$，得证。

参见

• 艾狄胥－斯通定理——图兰定理的推广，将禁止完全子图改为禁止图兰子图。