图兰定理

数学定理

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

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

叙述

若 G 是一个有 n 点的图,而且完全图 Kr+1 不是 G 的子图,则 G 最多有 条边。此外,如果 G 有 条边,则 G 一定是图兰图  

图兰图

定义

图兰图   的定义为一个特殊的具有 n 点的完全r-分图,其中各部分的顶点数的差不超过1,或者说,r 个部分分别有 个顶点。

性质

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

证明

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

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

定理证明

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

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

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

 

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

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

参见