奥尔定理

设 G 为（有限的）简单无向图，其顶点数 n ≥ 3。

奥尔定理表明，如果对每对 G 中的不相邻顶点对 v 和 w，均有

deg v + deg w ≥ n,

(∗)

那么 G 是哈密顿图。

式中，deg v 表示 G 中顶点 v 的度数（即与 v 相连的边数）。

此定理等价于：每个非哈密顿图 G 都不满足 (∗)。

设 G 是一个顶点数 n ≥ 3 的非哈密顿图。考虑是否有边不在 G 中，且加入 G 后，仍没有哈密顿回路。若有此种边，则选一条加入 G 中。如此重复，直到不能再加，得到的新图称为 H。令 x 、 y 为 H 中任意一对非邻接顶点，此时若向 H 中加入边 xy ，则图中将有哈密顿回路（否则先前加边的过程仍能继续）。这个回路中，除 xy 以外的其他边将形成一条哈密顿路径 v₁v₂...v_n，其中 x = v₁ 且 y = v_n。 对于 2 ≤ i ≤ n 范围内的每个 i ，考虑两条可能的边：从 v₁ 至 v_i 和从 v_{i − 1} 至 v_n，这两条边最多有一条存在于 H 中，否则 v₁v₂...v_{i − 1}v_nv_{n − 1}...v_i 会形成哈密顿回路。因此，v₁ 与 v_n 的度数之和最多等于 i 的可能取值数量，也就是 n − 1。这说明 H 不满足 (∗) ，因为 (deg v₁ + deg v_n) 小于 n。

但是，H 是由 G 加边（可能 0 条）而成，故 G 的顶点度不大于 H 中的顶点度数，所以 G 也不满足 (∗) 性质，得证。

需要注意的是，奥尔定理给出的是判定一幅图为哈密顿图的一个充分条件而非充要条件。换言之，一幅不满足奥尔定理条件的图仍有可能为哈密顿图。

例如，对于一个形如六边形的图（“6阶循环图”，为简单无向图），其任意两个不相邻的顶点度数之和为4（比6小），但显然该图是一个哈密顿图。

1997年，帕尔默（E. M. Palmer）发表以下算法，只要一幅图满足奥尔定理的条件，就能从中构造一个哈密顿回路：^[2]

1. 任意将顶点排成一个环形，无视邻接与否。
2. 若环上任意连续两个顶点皆已连边，则得到哈密顿环，算法结束。否则，可以找到环上有连续两个顶点 ${\displaystyle v_{i},v_{i+1}}$ ，在图中并不邻接，此时执行下列步骤：
   • 搜寻下标${\displaystyle j}$ ，使得四个顶点${\displaystyle v_{i},v_{i+1},v_{j},v_{j+1}}$ 两两互异，且图上有${\displaystyle v_{i}v_{j}}$ 与${\displaystyle v_{j+1}v_{i+1}}$ 两条边。
   • 将环${\displaystyle v_{i+1}}$ 至${\displaystyle v_{j}}$ 一段弧（含两端）倒转次序。
3. 回到2。

每次执行倒转时，环形上的边数必定增加${\displaystyle 1}$ 或${\displaystyle 2}$ （视乎过程中要拆散的${\displaystyle v_{j}v_{j+1}}$ 是否已经是边），所以至多执行${\displaystyle n}$ 次，算法就会停止，其中${\displaystyle n}$ 为顶点数。与上述证明类似，第2步若未得到哈密顿环，则所求的下标${\displaystyle j}$ 必定存在，否则顶点${\displaystyle v_{i}}$ 与${\displaystyle v_{i+1}}$ 既不邻接，其度数和又不够大，不满足奥尔定理的条件。${\displaystyle i}$ 和${\displaystyle j}$ 皆可将全部顶点扫描一次找到，时间复杂度用大O符号可以写成${\displaystyle O(n)}$ ，倒转弧${\displaystyle v_{i+1}}$ 至${\displaystyle v_{j}}$ 亦然。所以，乘上外层重复执行的次数，总时间复杂度为${\displaystyle O(n^{2})}$ ，与边数吻合。