图论证法集锦：归纳、构造、反证

摘要: 关于图的连通性的一些充分条件和必要条件

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

图论研究的对象是离散结构，因此关于图上的命题，证明方法一般为构造、归纳、反证。这三种方法可以解决大部分图上的证明问题。本文我们以图的连通性的一些命题为例，看一下这些证明技术具体怎样展开。

路径相关的概念

对于图 $G = (V, E)$ 来说，要定义清楚连通性的概念，首先需要搞清楚路径相关的一些概念，在中文书中，经常出现不同的书叫法不一样的情况，容易搞混，英文名称相对清楚一些，这里总结如下：

• 途径(walk)：图 $G$ 中一个点边交替的序列 $w=v_{i_{0}}e_{i_{1}}v_{i_{1}}e_{i_{2}}\cdots e_{i_{k}}v_{i_{k}}$ 称为图 $G$ 的一条途径，其中 $v_{i_{0}}$ 和 $v_{i_{k}}$ 分别称为途径 $w$ 的起点、终点。

• 迹(trail)：图 $G$ 中边不重复出现的途径称为迹。

• 路(path)：图 $G$ 中顶点不重复出现的迹称为路。

以上三个概念是递进关系，条件越来越强。当起点等于中点的时候，以上三个概念都对应一个类似于环的概念，分别为闭途径(closed walk)、闭迹(closed trail)、圈(cycle)。其中的边数称为长度。

导出子图

对于图 $G = (V, E)$ 来说，在定义连通分支的时候，涉及到导出子图的概念，这里我们把子图相关的概念复习一下。

• 子图(subgraph)：对于图 $G$ 和 $H$，如果 $V(H) \subseteq V(G)$ 且 $E(H) \subseteq E(G)$，则称图 $H$ 为 $G$ 的子图，记为 $H \subseteq G$。
• 生成子图(spanning subgraph)：若 $H\subseteq G$ 且 $V(H) = V(G)$ 则，则称 $H$ 为 $G$ 的生成子图。
• 点导出子图(induced subgraph)：$V’ \subseteq V(G)$，以 $V’$ 为顶点集，$G$ 中两顶点均属于 $V’$ 的所有边作为边集所组成的子图，称为 $G$ 的顶点集 $V’$ 的导出子图，记为 $G[V’]$。
• 边导出子图(edge-induced subgraph)：$E\subseteq E(G)$，以 $E’$ 为边集，以 $E’$ 中关联到的的所有顶点为顶点集所组成的子图，称为 $G$ 的边集 $E’$ 的导出子图，记为 $G[E’]$。

对于一些常用的特殊的子图，有一些简化的记号：

• $G-V’$ 表示从 $G$ 中删除顶点集 $V’$，关联的所有边也删除，所得的子图。
• $G-E’$ 表示从 $G$ 中删除边集 $E’$，但不删除关联的顶点，所得的子图。
• $G-v$ 表示 $G - \{v\}$；$G - e$ 表示 $G - \{e\}$。

有了路径以及导出子图的概念，可以定义清楚图的连通性与连通分支了。

连通性

给定图 $G = (V, E)$，对于 $u, v\in V$ 来说，如果从 $u$ 到 $v$ 有路相通，则称顶点 $u, v$ 在 $G$ 中连通。如果 $\forall u, v \in V$，$u, v$ 均在 $G$ 中连通，则 $G$ 称为连通图。

如果 $V(G)$ 可以划分为若干子集 $V_{1}, V_{2}, \cdot, V_{w}$ 使得两顶点数域同一子集当且仅当它们在 $G$ 中连通，则每个点导出子图 $G[V_{i}], i=1,2,\cdots,w$ 为图 $G$ 的一个连通分支，$w$ 为连通分支数。

由于连通性的概念非常重要，因此我们希望找到关于连通性的条件，包括连通的性质（必要条件），以及判定连通的方法（充分条件）。这方面的命题很多，

下面我们看三个相关的命题，证明方法分别涉及到归纳和反证，构造的思想穿插在其中。这刚好是图论证明中最常用的三个技术。

命题1（连通图的必要条件）

若图 $G$ 连通，则 $e(G) \geq v(G) - 1$。这里 $e(G)$ 表示边数，$v(G)$ 表示点数。

证明（数学归纳法）

对顶点数 $v$ 用数学归纳法。

对于 $v = 1, 2$，$e \geq v - 1$ 成立。

假设 $v \leq k$ 的连通图都有 $e \geq v - 1$。

对于 $v = k + 1$ 的连通图 $G$，任取 $v \in V(G)$，考虑子图 $G - v$。

若 $G - v$ 连通，则由归纳假设，$e(G-v) \geq v(G-v) - 1 = k - 1$。而由于 $G$ 连通，还有 $v$ 与 $G - v$ 相连的至少一条边，因此：

$$e(G) \geq e(G-v) + 1 \geq (k-1) + 1 = k = v(G) - 1$$

若 $G-v$ 不连通，假设 $G_{1}, G_{2}, \cdots, G_{w}$ 为其连通分支 $w \geq 2$。由归纳假设，$e(G_{i}) \geq v(G_{i}) - 1, i=1,2,\cdots,w$，因此：

$$e(G-v) = \sum\limits_{i=1}\limits^{w}e(G_{i}) \geq \sum\limits_{i=1}\limits^{w}v(G_{i}) - w = v(G - v) - w = k - w$$

由于 $G$ 连通，$v$ 与 $G-v$ 的 $w$ 个连通分支均有至少一条边，加起来还有至少 $w$ 条边，因此：

$$e(G) \geq e(G-v) + w \geq (k - w) + w = (k+1) - 1 = v(G) - 1$$

$\Box$

命题2（连通图的充分条件）

图 $G$ 为简单图，有 $2n$ 个顶点，最小顶点度为 $\delta(G) \geq n$，则 $G$ 是连通图。

证明（反证法）

假设 $G$ 不连通，那么连通分支数 $w \geq 2$。

将连通分支视为盒子，将顶点视为物品，由鸽巢原理，至少有一个连通分支中的顶点数不超过 $n$。

鸽巢原理

设 $q_{1}, q_{2},\cdots,q_{n}$ 为正整数，将 $q_{1} + q_{2} + \cdots + q_{n} - n + 1$ 个物品放入 $n$ 个盒子，则或者第 $1$ 个盒子至少有 $q_{1}$ 个物品，或者第 $2$ 个盒子有至少 $q_{2}$ 个物品，…，或者第 $n$ 个盒子有至少 $q_{n}$ 个物品。

那么在该顶点数不超过 $n$ 的连通分支中，顶点度最多为 $n-1$，与 $\delta(G) \geq n$ 矛盾。

$\Box$

考虑 $2n$ 台机器，每台机器至少与 $n$ 台其它机器直接相连，则这 $2n$ 台机器中任意两台机器之间均可通信。

关于鸽巢原理，参考文章 鸽巢原理及其加强形式。

命题3（两点连通的充分条件）

若图 $G$ 恰有两个奇度顶点，则这两个顶点一定连通。

证明（反证法）

设 $u, v$ 为 $G$ 中恰好的两个奇度顶点。假设 $u, v$ 不连通，则 $u, v$ 属于不同的 2 个连通分支。

将这两个连通分支分别视为一个图时，该图中的奇度顶点恰好是 1 个，这与图论第一定理的推论矛盾。

定理(图论第一定理、握手定理)

对于任意有向图 $D$ 均有：

$$\sum\limits_{x\in V(D)}d_{D}^{+}(x) = \sum\limits_{x\in V(D)}d_{D}^{-}(x) = \epsilon(D)$$

其中 $d_{D}^{+}(x)$ 表示 $x$ 的出度、$d_{D}^{-}(x)$ 表示 $x$ 的入度。该定理说的是对于任意有向图，总出度等于总入度等于总边数。

推论

任意无向图 $G$ 的奇度点为偶数个。

$\Box$

关于图论第一定理，可以参考文章 伴随二部图、图论第一定理。

总结

本文我们讨论了图的连通性相关的命题，顺便回顾了图论中的一些概念，以及图论证明中的最常用的技术：归纳、反证、构造。

---