非哈密頓圖

非哈密頓圖是指不是 哈密頓圖 的圖。所有 非連通圖 因此都是非哈密頓圖，無環圖 也是如此。

屬於連通圖且為非哈密頓圖的類別包括 啞鈴圖、齒輪圖、舵輪圖、次哈密頓圖、皮划艇槳圖、棒棒糖圖、門格海綿圖、平底鍋圖、非平凡 路徑圖、斯納克圖、星圖、太陽圖、小太陽圖、蝌蚪圖、非平凡 樹 、弱斯納克圖、網狀圖 和 風車圖。

可以使用 Wolfram 語言確定圖是否為非哈密頓圖，方法是使用HamiltonianGraphQ[g]，並且可以使用以下命令獲取許多命名圖的預計算值GraphData[graph,"Nonhamiltonian"].

節點數為 , 2, ... 的連通簡單非哈密頓圖的數量為 0, 1, 1, 3, 13, 64, 470, 4921, ... (OEIS A126149)，其中前幾個如上圖所示，而節點數為 , 2, ... 的不必連通的簡單非哈密頓圖的相應數量為 0, 2, 3, 8, 26, 108, 661, 6150, 97585, ... (OEIS A246446)。

在 10 個或更少節點的 多面體圖 中沒有非哈密頓圖，對於 , 12, ... 節點的數量為 74, 1600, 43984, 1032208, 22960220, ... (OEIS A007033)。11 節點圖中最著名的是 Herschel 圖 和 Goldner-Harary 圖。

下表總結了一些小的命名連通非哈密頓圖。

圖
單點圖	1
爪形圖	4
Theta-0 圖	7
彼得森圖	10
赫舍爾圖	11
無完美匹配圖	16
第一個 Blanuša 斯納克圖	18
第二個 Blanuša 斯納克圖	18
花斯納克圖	20
考克斯特圖	28
雙星斯納克圖	30
托馬森圖	34
塔特圖	46
塞凱賴什斯納克圖	50
梅雷迪思圖	70