極大非哈密頓圖

極大非哈密頓圖是一個 非哈密頓圖 ，對於它的補圖 中的每條邊 ， 是 哈密頓圖，即，每兩個不相鄰的頂點都是一條哈密頓路徑的端點。

由於在不連通圖的兩個不連通分量之間新增一條邊會形成橋，並且在沿一個方向穿過橋後，哈密頓環不能“穿回”另一個方向，因此可以看出，只有連通的非哈密頓圖才能是極大非哈密頓圖。

路徑圖 的狀態是有爭議的，因為它是非哈密頓圖，但具有空補圖，但根據嚴格的解釋，“其補圖的所有 0 條邊都產生哈密頓圖”，它應被視為極大非哈密頓圖。

頂點數為 , 2, ... 的極大非哈密頓圖的數量分別為 0, 1, 1, 1, 3, 3, 7, 9, 18, 31, ... (OEIS A185306)，其中前幾個示例如上所示。更大的例子包括 Coxeter 圖、奇數 的 花snark圖 、Petersen 圖和 Tietze 圖 (Clark and Entringer 1983)。