Dirac定理

概述

Dirac定理（Dirac’s Theorem）：若简单图 $G$ 有 $n \geq 3$ 个顶点且每个顶点的度数 $de g (v) \geq n /2$ ，则 $G$ 中存在一条哈密顿回路。

定理陈述

形式化陈述

定理（Dirac, 1952）：设 $G = (V, E)$ 是一个简单图， $∣ V ∣ = n \geq 3$ 。若对 $G$ 中每个顶点 $v$ 都有 $de g (v) \geq n /2$ ，则 $G$ 中存在一条哈密顿回路。

证明思路

证明采用最长路径论证法（longest path argument），核心思想如下：

设 $P = v_{1} v_{2} \dots v_{k}$ 是 $G$ 中一条最长的路径（即无法再向两端延伸的路径）。由于 $P$ 是最长的， $v_{1}$ 和 $v_{k}$ 的所有邻接点都必须在 $P$ 上。

定义两个集合： $S = {i : v_{1} v_{i + 1} \in E, 1 \leq i \leq k - 1}$ $T = {i : v_{i} v_{k} \in E, 2 \leq i \leq k}$

由于 $de g (v_{1}) \geq n /2$ 且 $de g (v_{k}) \geq n /2$ ，有 $∣ S ∣ \geq n /2$ ， $∣ T ∣ \geq n /2$ 。

$S$ 和 $T$ 都是 ${1, 2, \dots, k - 1}$ 的子集，且 $∣ S ∣ + ∣ T ∣ \geq n \geq k$ 。由鸽巢原理， $S \cap T \neq = \emptyset$ 。

设 $j \in S \cap T$ ，则 $v_{1} v_{j + 1} \in E$ 且 $v_{j} v_{k} \in E$ 。

由此可以构造回路： $C = v_{1} v_{j + 1} v_{j + 2} \dots v_{k} v_{j} v_{j - 1} \dots v_{2} v_{1}$

若 $k < n$ ，由于 $G$ 是连通的（ $δ (G) \geq n /2$ 保证连通性），存在不在 $P$ 上的顶点与 $P$ 上的某顶点相邻，这与 $P$ 是最长路径矛盾。因此 $k = n$ ， $C$ 是哈密顿回路。

Dirac, G. A. (1952). Some theorems on abstract graphs. Proc. London Math. Soc., s3-2(1), 69-81.
证明详解: Mathematics LibreTexts - Hamilton Paths and Cycles
多种证明方法: Dirac’s Theorem on Hamiltonian Graphs

推论1：完全图 $K_{n}$ （ $n \geq 3$ ）一定是哈密顿图（因为 $de g (v) = n - 1 \geq n /2$ ）
推论2：Dirac定理是Ore定理的特殊情形——当 $de g (u) + de g (v) \geq n$ 对所有不相邻顶点成立时，若每个顶点度数都 $\geq n /2$ ，条件自然满足
推论3：满足Dirac条件的图一定是连通图（因为任意两个不相邻顶点的度数之和 $\geq n$ ，不可能被割集分离）