非哈密顿图

非哈密顿图是指不是 哈密顿图 的图。所有 非连通图 因此都是非哈密顿图，无环图 也是如此。

属于连通图且为非哈密顿图的类别包括 哑铃图、齿轮图、舵轮图、次哈密顿图、皮划艇桨图、棒棒糖图、门格海绵图、平底锅图、非平凡 路径图、斯纳克图、星图、太阳图、小太阳图、蝌蚪图、非平凡 树 、弱斯纳克图、网状图 和 风车图。

可以使用 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