奧爾定理是圖論在1960年由挪威數學家奧斯汀·奧爾證明的結果,它為圖成為哈密頓量提供了充分的條件 [1] ,從本質上說,具有「足夠多的邊」的圖必須包含哈密頓環。具體來說,該定理考慮非相鄰頂點對的度數之和:如果每個這樣的對具有至少等於圖中頂點總數的和,則該圖為哈密頓圖。
如果一個總點數至少為3的簡單圖G滿足:G的任意兩個不相鄰的點u和v度數之和至少為n,即deg(u)+deg(v)≥n,那麼G必然有哈密頓迴路。
表達了一個簡單圖中只要有足夠多的邊就一定包含哈密頓迴路。類似的還有狄拉克定理:每個頂點度數大於等於n/2;
它描述了簡單圖擁有哈密頓迴路的一個充分條件。到2020年還未發現任何關於哈密頓迴路存在性的任何充分必要條件
令G為有n≥3個頂點的簡單有限圖。我們用度deg表示G中頂點v的度,即G到v中的入射邊數。然後,Ore定理指出 : [1]
對G中每對不同的非相鄰頂點v和w,都有deg(v) + deg(w) ≥ n (*)
那麼G是哈密頓圖
等效地表明,每個非哈密頓圖G都不滿足條件(*)。 [1] 因此,令G為非哈密頓圖的 n≥3 個頂點上的圖,並通過一次不增加哈密頓邊數加一個邊,由G形成H,直到無法再增加邊。令x和y為H中的任何兩個不相鄰的頂點。然後將邊xy添加到H,將創建至少一個新的哈密頓迴路,並且在H中的此迴路中的xy以外的邊一定會形成哈密頓路徑v_1, v_2, ... v_n,(x = v_1,y = v_n)。對於2≤i≤n範圍內的每個指數i,考慮H中從v_1到v_i和從v_(i-1)到v_n的兩個可能邊。在H中最多可以存在這兩個邊之一,否則周期v_1,v_2 ... v_(i-1), v_n, v_(n-1) ... vi將是哈密頓迴路。因此,入射到v_1或v_n的邊的總數最多等於 i 的選擇數,即n-1。因此,H不服從屬性(*),這要求該邊的總數(deg(v_1) + deg(v_n))大於或等於n。由於G的頂點度最多等於H的度數,因此得出G也沒有服從特性(*)的結論。