第八十二讲 托兰定理 讲义-2026年高中数学竞赛

第八十二讲  托兰定理

1941 年，匈牙利数学家托兰(Turán)解决了如下的问题:一个 阶简单图 若不包含 子图,则最多有多少条边? 这个问题的结论即是著名的托兰定理。托兰定理开创了图论中研究禁用子图的极值图论的广泛领域。这类问题通常形式是讨论当 不含某种子图时,至多有多少边,或等价地,当 的边数至少为多少时,则一定会有某种结构的子图。在本节中我们列举一些这样的问题, 并且可以看到在组合的很多方面都有其应用。

1. 托兰定理

若 个整数两两之差不超过 1,称这 个整数是几乎相等的。易知将正整数 写成 个几乎相等的整数之和的方法是唯一的(不考虑顺序): 作带余除法 , ,则 ,即 可以写成 个 和 个 之和。

将 个顶点的集合 划分成 个部分 ,使各部分的点数几乎相等,以 为分部作完全 部图,称为托兰图,记为 。显然任何 部图均不含 子图。记 的边数为 ,

托兰定理 设 是正整数, 是 阶简单图,且不含 子图。则 ,等号成立当且仅当 。

证明 对 归纳证明结论。 时, 不含 子图, 是空图, 也是空图,结论成立。

假设 ,且结论对 成立。设 是不含 子图的 阶

简单图, 且 的边数达到最大值。设 是 中度最大的一个顶点,设 , 。我们分几步证明。

(i) ,且 。

由于 与 中每个顶点相邻, 不含 子图,由归纳假设可知 。我们另作一个图 ,顶点集也是 ,在 上构造托兰图 ,并将 中每个顶点与 中每个顶点均连边。 是一个完全 部图,从而不含 子图。比较 与 的边数,在 上, 边数不超过 的边数。对 ,

因此

①

而由于 的边数取得最大值,必有 ,从而 的边数等于 的边数,且 。由于 不含 子图,且边数为 ,由归纳假设得 。

(ii) 。

在 (i) 中已经证明 的边数等于 的边数,注意 是完全 部图。设 的各部分点数分别为 。将 分为 个几乎相等的数为 ,利用组合数的凸性可知,

②

从而 。由于 不含 子图,且边数为 ,由 的边数最大性可知 。

(iii) 。

在 (ii) 中已经证明 ,并且由组合数的凸性以及②取等号,可知 的各部分的点数是几乎相等的,因此 。我们再次回顾(i) 中关于 和 的边数的比较,有 之间互不相邻,否则①中第一个不等号是严格的。这样对 ,再由 可知 。

综上所述，在 时结论也成立。由数学归纳法，托兰定理成立。

托兰定理在 时的情形在更早时(1907 年)由曼特尔(Mantel)给出:不含三角形的 阶简单图的边数不超过 ，且等号成立时是完全二部图 。

2. 应用举例

例 1 设 是一个 20 阶简单图,且 恰含一个三角形。求 的边数的最大可能值。

解 答案是 92 。

首先证明边数不超过 92 。设 ,唯一的三角形为 ,则对 中任意一点 ,至多与 中一个顶点相邻,因此 17。又 不含三角形,由托兰定理, 。因此

下面我们给出 92 条边的例子。取 19 个顶点 ,连 90 条边 。再取一个顶点 ,连边 。在这个 92