图兰定理

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

定义

图兰图 ${\displaystyle T_{n,r}}$  的定义为一个特殊的具有 n 点的完全r-分图，其中各部分的顶点数的差不超过1，或者说，r 个部分分别有${\displaystyle \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-分图中，图兰图 ${\displaystyle T_{n,r}}$ 是唯一一个边数最多的图。

证明

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

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

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

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

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

${\displaystyle |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 是图兰图 ${\displaystyle T_{n,r}}$ ，得证。

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