双三次非哈密顿图

双三次非哈密顿图是一个双三次（即，二分 三次图），它是非哈密顿的（即，不具备哈密顿环）。

Tutte (1971) 猜想所有 3-连通 双三次图 都是 哈密顿图，这一论断被称为 Tutte 猜想。Horton 图，包含 96 个节点，如上图所示，提供了第一个反例 (Bondy and Murty 1976, p. 240)。

Horton (1982) 随后找到了一个包含 92 个节点的反例，Ellingham (1981, 1982b) 和 Owens (1983) 发现了两个更小的（非同构）包含 78 个节点的反例。Ellingham 和 Horton (1983) 随后发现了一个包含 54 个节点和 81 条边的反例图。目前已知的最小反例是 50 节点的 Georges 图 (Georges 1989; Grünbaum 2006, 2009)。

这些已知的小反例总结在下表中，并在上面进行了说明。

	名称	参考文献
50	Georges 图	Georges (1989), Grünbaum (2006, 2009)
54	54-Ellingham-Horton 图	Ellingham and Horton (1983)
78	78-Ellingham-Horton 图	Ellingham (1981, 1982)
78	78-Owens 图	Owens (1983)
92	92-Horton 图	Horton (1982)
96	96-Horton 图	Bondy and Murty (1976)