8.4 Ore定理(1962)

Ore定理的内容是：
对于n个节点的简单图（n>2），如果每一对非相邻节点的度数和至少为n，那么这个图是哈密尔顿图。
这个定理其实是不实用的，条件太苛刻，但是作为一个著名的定理，这里我还是给出证明过程。首先一定要至少三个点，因为两点成环，必须存在平行边，这个就不需要证明了，下面正式进入证明环节。
利用反证法证明，首先假设满足上述条件的图G不是哈密尔顿图。既然不是哈密尔顿图，那么我们就增加边，让它慢慢变成哈密尔顿图。假设最后在x和y两点加了一条边，形成了哈密尔顿图，把这个图成为$G_{last}$,而增加之前的成为$G_{before}$。
所以在$G_{before}$上x和y是不相连的。假设$G_{before}$这条哈密尔顿路径是$z_1$到$z_n$。根据前面证明狄拉克定理用到的鸽笼原理，或者叫鸽巢原理。$z_1$到$z_n$之间有n-2个位置，但是他们入度和，或者说邻居总和是n，所以和狄拉克定理的证明一样，一定存在一个点是$x_0$的邻居而路径上下一个点是$x_n$的邻居。那么证明了$G_{before}$就存在哈密尔顿环路，与假设矛盾。Q.E.D.(证明完毕)
可以说，Dirac定理是奥尔定理的一个特殊场景。但是仔细比较发现，Dirac定理发表于1952年，而Ore定理发表于1962年，整整十年时间，才从特殊到了一般。可见数学是一条崎岖坎坷的路。