图论方法

一句话

把对象画成顶点，把“有关系”画成边，题目就变成一张图。图论里最朴素的一条定理：

v \sum de g v = 2 \times (边数)

（每条边连着两个顶点，被数了两次——这是“算两次”在图上的样子。）于是奇度数的顶点一定有偶数个。再加上边的染色（认识 / 不认识）和三角形，许多“任意 $n$ 个人……”的题目就有了直观的模型。

先猜后证

$9$ 个人能不能每人都恰好与其中 $3$ 人握过手？

能不能

先选定答案，才能看到结论。

例：任意 6 人中，必有 3 人两两认识或两两不认识（经典的拉姆齐问题）

第 1 / 5 步

建模
人 → 顶点；两人认识 → 红边，不认识 → 蓝边。要证： $6$ 个顶点的完全图 $K_{6}$ 的任意二染色都有单色三角形。

$认识 = 红, 不认识 = 蓝$
5 个人不够
看一个顶点
看这三个人之间
否则全是蓝的

第 1 站 · 子集族：相交关系图（卷一）

集合族里“两个集合相交”是一种两两关系。把集合画成顶点，握手定理就能回答存在性问题。

例：能否找到 7 个集合，使每个集合恰与其余集合中的 3 个相交？

第 1 / 3 步

画成图
每个集合是一个顶点，两个集合相交就连一条边。条件变成： $7$ 个顶点，每个顶点度数为 $3$ 。

$de g A_{i} = 3 (i = 1, \dots, 7)$
握手定理
矛盾

第 2 站 · 集合的分划：二部图与奇圈（卷一）

把顶点分成两组，使每条边都跨组——这就是二部图。能不能分，取决于有没有奇圈。

7

个人围坐一圈，每人和左右邻居合不来（连边）。想把他们分进两个房间，使合不来的人不同屋。试着在纸上沿圈交替标 A、B——走一圈回来会怎样？

沿着圈交替分组 A、B、A、B……，走 $7$ 步回到起点时，起点应该是 B——而它是 A。所以奇圈不能二分组。反过来可以证明：没有奇圈的图一定能二分组（从任一顶点出发，按距离的奇偶分组）。

第 3 站 · 组合计数估计：没有三角形的图（卷六）

6

个顶点、

9

条边，没有三角形。再加任何一条边会怎样？

一题多解

$n$ 个顶点的图中没有三角形。证明边数 $e \leq \frac{n ^{2}}{4}$ （曼特尔定理）。

算两次 + 柯西

对每条边 $uv$ ： $u, v$ 没有公共邻点（否则成三角形），所以 $de g u + de g v \leq n$ 。对所有边求和，每个顶点 $v$ 在它的 $de g v$ 条边里各出现一次： $\sum_{v} (de g v)^{2} \leq n e$ 。由柯西不等式 $\sum (de g v)^{2} \geq \frac{( \sum de g v ) ^{2}}{n} = \frac{4 e ^{2}}{n}$ 。所以 $\frac{4 e ^{2}}{n} \leq n e$ ， $e \leq \frac{n ^{2}}{4}$ 。

代价思路清楚，用到卷六的柯西不等式。

极端原理

取度数最大的顶点 $v$ ， $de g v = d$ 。 $v$ 的 $d$ 个邻点两两不相邻，所以每条边至少有一个端点在其余 $n - d$ 个顶点中，而这些顶点的度数都 $\leq d$ ： $e \leq d (n - d) \leq \frac{n ^{2}}{4}$ 。

代价不用不等式，但要想到取度数最大的顶点。

等号由完全二部图取到：两组各 $\frac{n}{2}$ 个顶点，组间全连，组内不连——上图就是 $n = 6$ 的情形， $9 = \frac{36}{4}$ 。

练一练

练习 1基础

$10$ 个人聚会，每人恰好与其中 $3$ 人握手。一共握了多少次手？

练习 2基础

$10$ 个顶点的图中没有三角形，边数最多是多少？

练习 3提高

用红、蓝两色给完全图 $K_{n}$ 的每条边染色。要使无论怎样染都一定有单色三角形， $n$ 最小是多少？

练习 4挑战

$K_{6}$ 的边任意染红、蓝两色。单色三角形至少有几个？

一句话

例：任意 6 人中，必有 3 人两两认识或两两不认识（经典的拉姆齐问题）

第 1 站 · 子集族：相交关系图（卷一）

例：能否找到 7 个集合，使每个集合恰与其余集合中的 3 个相交？

第 2 站 · 集合的分划：二部图与奇圈（卷一）

第 3 站 · 组合计数估计：没有三角形的图（卷六）

算两次 + 柯西

极端原理

练一练

错误博物馆 · 本站展品

握手只数了一次

以为 5 个人也躲不开

这条线路经过的站