Hamilton 通路和回路的充分条件

对于图 $G$ ，若存在一条路径恰好经过每个顶点一次，该通路叫做 Hamilton 通路；若存在一条回路恰好经过每个顶点一次（始末点除外），该通路叫做 Hamilton 回路。

没有已知简单的充要条件可以判断 Hamilton 通路或回路是否存在，不过，人们发现，图 $G$ 中的边数越多，就越可能存在 Hamilton 通路和回路。特别是，当图 $G$ 已经存在 Hamilton 通路或回路时，若再向图中加新的边（但不增加顶点），新图中依然存在 Hamilton 通路或回路。我们有理由认为，当图中顶点的度数充分大时，Hamilton 通路或回路一定存在。本文将介绍并证明几个和顶点度数相关的充分条件。

Hamilton 通路存在的充分条件

定理：令 $G = (V, E)$ 为简单图，其中 $| V | = n \geq 3$ 。若对于每一对不相邻的顶点 $(u, v)$ ，都有 $\deg (u) + \deg (v) \geq n - 1$ ，则 $G$ 中存在 Hamilton 通路。

证明：首先证明 $G$ 是连通图。若 $G$ 不连通，令 $C_{1}$ 、 $C_{2}$ 为 $G$ 的其中两个连通分量，分别有 $n_{1}$ 、 $n_{2}$ 个顶点。令 $u$ 是 $C_{1}$ 中的顶点， $v$ 是 $C_{2}$ 中的顶点。由于 $G$ 是简单图， $C_{1}$ 、 $C_{2}$ 也是简单图，即无重边、无环。则有

\begin{array}{r} \deg (u) \leq n_{1} - 1 \\ \deg (v) \leq n_{2} - 1 \end{array}

两式相加，得：

\begin{array}{r} \deg (u) + \deg (v) \leq n_{1} + n_{2} - 2 \leq n - 2 \end{array}

这与已知条件矛盾。因此 $G$ 必定连通。

下面，我们要在连通图 $G$ 中构造出一条 Hamilton 通路。先约定记号 $p_{m}$ 为长度为 $m - 1$ 的简单路径（无重复顶点） ${v_{1}, v_{2}}$ , ${v_{2}, v_{3}}$ , $\dots$ , ${v_{m - 1}, v_{m}}$ $(m \geq 2)$ 。 $p_{2}$ 必定存在，因为 $G$ 连通，即任意顶点 $v_{1}$ 都与至少一个其他顶点 $v_{2}$ 与之相连，取路径 ${v_{1}, v_{2}}$ 作为 $p_{2}$ 即可。 $p_{n}$ 即为我们要找的 Hamilton 通路。现在我们需要证明，对于任意简单路径 $p_{m} (2 \leq m \leq n - 1)$ ，都有办法将其扩展为更长的路径，直到找到 $p_{n}$ 为止。我们分以下几种情况讨论。

1. $v_{1}$ 或 $v_{m}$ 与 $p_{m}$ 外的任一顶点相邻。假设 $v_{1}$ 与 $p_{m}$ 外的顶点 $v$ 相邻，则只需将边 ${v_{1}, v}$ 并入 $p_{m}$ ，再将所有顶点重新标号，即可得到 $p_{m + 1}$ 。若是 $v_{m}$ 与 $v$ 相邻，同理。

2. $v_{1}$ 和 $v_{m}$ 都只与 $p_{m}$ 内的顶点相邻。下面会证明，在这种情况下， $p_{m}$ 中的所有顶点一定组成一条简单回路（无重复顶点）。先约定记号 $S$ 为 $p_{m}$ 中与 $v_{1}$ 相邻的所有顶点组成的集合， $| S | = k$ 。

若 $\exists v_{t} \in S$ ，使得 $v_{t - 1}$ 与 $v_{m}$ 相邻，我们只需添加边 ${v_{1}, v_{t}}$ 和 ${v_{t - 1}, v_{m}}$ ，再删除边 ${v_{t - 1}, v_{t}}$ 即可得到由 $p_{m}$ 的所有顶点组成的简单回路，如下图所示。（该情况包含了 $v_{1}$ 与 $v_{m}$ 相邻的情形。）
若 $! \exists v_{t} \in S$ ，使得 $v_{t - 1}$ 与 $v_{m}$ 相邻，则在 ${v_{1}, v_{2}, \dots, v_{m - 1}}$ 中，至少有 $k$ 个顶点不与 $v_{m}$ 相邻。又因为 $v_{m}$ 只与 $p_{m}$ 内的顶点相邻，所以 $\deg (v_{m}) \leq m - 1 - k$ 。又因为 $\deg (v_{1}) = k$ ，两式相加，得到 $\deg (v_{1}) + \deg (v_{m}) \leq m - 1 < n - 1$ ，这与已知条件矛盾。所以该情况不存在。

现在我们证明了 $p_{m}$ 中的所有顶点形成简单回路。任取 $p_{m}$ 之外的任意顶点 $v$ ，由图的连通性，一定存在一条连接 $v$ 和 $p_{m}$ 上某顶点 $v_{r}$ 的路径。将该路径中所有边添加进 $p_{m}$ ，删掉原回路中任一条以 $v_{r}$ 为端点的边，再将所有顶点重新标号，即可得到 $p_{m + l}$ ， $l$ 为 $v$ 到 $p_{m}$ 的最短距离，如下图。

Distance

综合 1、2 两种情况，我们证得，对于任意路径 $p_{m} (2 \leq m \leq n - 1)$ ，都有办法将其扩展为更长的路径，直到找到 $p_{n}$ 。因此 Hamilton 通路存在。∎

Hamilton 回路存在的充分条件

Ore 定理

令 $G = (V, E)$ 为简单图，其中 $| V | = n \geq 3$ 。若对于每一对不相邻的顶点 $(u, v)$ ，都有 $\deg (u) + \deg (v) \geq n$ ，则 $G$ 中存在 Hamilton 回路。

证明：该定理实际上是增强了上节定理中的条件。我们直接利用上节中的定理来证明。

由于 $\deg (u) + \deg (v) \geq n > n - 1$ ，所以 $\deg (u) + \deg (v) \geq n - 1$ 。由上节定理，我们可以直接证得图 $G$ 中存在 Hamilton 通路 $p_{n}$ 。现在，我们用类似上节中第二种情况的方法，证明 $p_{n}$ 中的所有顶点可以构成 Hamilton 回路。先约定记号 $S$ 为 $p_{n}$ 中与 $v_{1}$ 相邻的所有顶点组成的集合， $| S | = k$ 。

若 $\exists v_{t} \in S$ ，使得 $v_{t - 1}$ 与 $v_{n}$ 相邻，我们只需添加边 ${v_{1}, v_{t}}$ 和 ${v_{t - 1}, v_{n}}$ ，再删除边 ${v_{t - 1}, v_{t}}$ 即可得到由 $p_{n}$ 的所有顶点组成的简单回路。（该情况包含了 $v_{1}$ 与 $v_{n}$ 相邻的情形。）
若 $! \exists v_{t} \in S$ ，使得 $v_{t - 1}$ 与 $v_{n}$ 相邻，则在 ${v_{1}, v_{2}, \dots, v_{n - 1}}$ 中，至少有 $k$ 个顶点不与 $v_{n}$ 相邻，所以 $\deg (v_{n}) \leq n - 1 - k$ 。又因为 $\deg (v_{1}) = k$ ，两式相加，得到 $\deg (v_{1}) + \deg (v_{n}) \leq n - 1$ ，这与已知条件矛盾。所以该情况不存在。

综上， $p_{n}$ 中的所有顶点可以构成 Hamilton 回路。Hamilton 回路存在。∎

Dirac 定理

令 $G = (V, E)$ 为简单图，其中 $| V | = n \geq 3$ 。若对于任一顶点 $u$ ，都有 $\deg (u) \geq ⌈ \frac{n}{2} ⌉$ ，则 $G$ 中存在 Hamilton 回路。

证明：该定理条件蕴含了 Ore 定理的条件，由 Ore 定理成立，得 Dirac 定理成立。∎