哈密顿道路与回路相关结论

· · 个人记录

定理 1

如果无向简单图 G 中的任意两个结点 v_i, v_j 之间恒有 \deg v_i+\deg v_j \geq n-1，则 G 中存在哈密顿道路。

证明：

  1. 若不连通，从两个连通块中各选出一个点，他们的 $\deg$ 和 $\leq n-2$。矛盾。
  2. 若 $P=(v_{i_1}, v_{i_2}, \ldots, v_{i_l})$ 为极长初级道路且 $l \neq n$，我们考虑 $v_{i_1}$ 和 $v_{i_l}$，他们的 $\deg \geq n-1$。对 $(v_{i_k}, v_{i_{k+1}}), 1 \leq k < l$ 这 $l-1$ 条边使用抽屉原理，其中必有一对点 $(v_a, v_b)$ 满足 $v_b$ 与 $v_{i_1}$ 相连，$v_{a}$ 与 $v_{i_l}$ 相连。 此时我们令 $C=(v_{i_1}, v_{i_2}, \ldots, v_{a}, v_{i_l}, v_{i_{l-1}}, v_{i_{l-2}}, \ldots, v_b, v_{i_1})$，可知 $C$ 是简单环。 由于 $G$ 是连通的，则存在不在 $P$ 中的点 $w$ 与 $P$ 中的某点相连。 我们将环在此断开，连上这个点得到了一条长度为 $l+1$ 的极长初级道路。 与 $l \neq n$ 的前提假设矛盾。故存在哈密顿道路。

推论

  1. 如果无向简单图 G 中的任意两个结点 v_i, v_j 之间恒有 \deg v_i+\deg v_j \geq n，则 G 中存在哈密顿回路。

    这是因为我们可以在 l=n 时也找出来一个简单环 C。

  2. 如果无向简单图 G 中的任意结点 v 恒有 \deg v \geq \lceil\frac n2\rceil，则 G 中存在哈密顿回路。（2021 茶园二招）

  3. 如果无向简单图 G 中存在两个结点 v_i, v_j 满足 \deg v_i+\deg v_j \geq n，则 G 中存在哈密顿回路的充要条件是 G+(v_i, v_j) 有哈密顿回路。

    必要性显然。充分性考虑若 G 不存在回路，说明 G+(v_i, v_j) 的回路必经 (v_i, v_j)，删去这条边后我们得到了一条哈密顿道路，由于 \deg v_i+\deg v_j \geq n，我们可以找到一个环 C。

定理 2

如果无向简单平面图 G 中存在哈密顿道路，则我们可以用 4 种颜色给 G 划分出的所有有界区域染色，满足相邻区域的颜色不同。

证明：

  1. 回路将平面划分为里（回路包住的有界区域）外两部分，每一部分都存在这部分所有区域的一个排列 p_1, p_2, \ldots, p_k，使得仅有 (p_1, p_k) 和 (p_i, p_{i+1}), 1 \leq i < k 有可能相邻。

    考虑若不存在，则存在三个区域两两相邻。这三个区域必然存在一个内部的交点，这个交点不在回路上，与回路的定义矛盾。

  2. 在上述条件下，内外都可以只用两种颜色染色。