哈密顿图

经过图中每个结点一次仅仅一次的基本通路称为哈密顿通路

通过图中所有顶点一次且仅一次的基本回路称为哈密顿回路

具有哈密顿回路的图称为哈密顿图

具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图

设 $G = ⟨ V, E ⟩$

若 G 是哈密顿图，对于 V 的任意非空子集 $V_{1}$ ，则 $p (G - V_{1}) \leq ∣ V_{1} ∣$
- 找到一条哈密顿回路 C，因为减边了，所以连通分支肯定不减少，只要证明 $p (C - V_{1}) \leq ∣ V_{1} ∣$
- 因为在环上删结点，最坏情况是删的点不相邻（有连边），形成的连通分支最多为 $∣ V_{1} ∣$
若 G 是半哈密顿图，对于 V 的任意非空子集 $V_{1}$ ，则 $p (G - V_{1}) \leq ∣ V_{1} ∣ + 1$
- 证明同上，不过环变成了一条链
完全图 $K_{2 k + 1}$ 中含有 $k$ 条边不重复的哈密顿回路
完全图 $K_{2 k}$ 中含有 $k - 1$ 条边不重复的哈密顿回路，从 $K_{2 k}$ 中删除这 $k - 1$ 条边不重复的回路后所得到的图含有 $k$ 条不相邻的边

利用图的着色，相邻不同色（可能可以构造），最后数两种颜色个数差，若大于 1 则不可能构造哈密顿通路

G 是无向简单图（ $n \geq 2$ ），如果对于任意两个不相邻的结点都有 $d e g (v_{i}) + d e g (v_{j}) \geq n - 1$ ，则 G 中存在哈密顿通路，即为半哈密顿图

G 是无向简单图（ $n \geq 3$ ），如果对于任意两个不相邻的结点都有 $d e g (v_{i}) + d e g (v_{j}) \geq n$ ，则 G 中存在哈密顿回路，即为哈密顿图

推论 G 是无向简单图（ $n \geq 3$ ），如果对于任意两个不相邻的结点都有 $d e g (v_{i}) \geq \frac{n}{2}$ ，则 G 中存在哈密顿回路，即为哈密顿图

🪴 Cyril