极大非哈密顿图

极大非哈密顿图是一个 非哈密顿图 ，对于它的补图 中的每条边 ， 是 哈密顿图，即，每两个不相邻的顶点都是一条哈密顿路径的端点。

由于在不连通图的两个不连通分量之间添加一条边会形成桥，并且在沿一个方向穿过桥后，哈密顿环不能“穿回”另一个方向，因此可以看出，只有连通的非哈密顿图才能是极大非哈密顿图。

路径图 的状态是有争议的，因为它是非哈密顿图，但具有空补图，但根据严格的解释，“其补图的所有 0 条边都产生哈密顿图”，它应被视为极大非哈密顿图。

顶点数为 , 2, ... 的极大非哈密顿图的数量分别为 0, 1, 1, 1, 3, 3, 7, 9, 18, 31, ... (OEIS A185306)，其中前几个示例如上所示。更大的例子包括 Coxeter 图、奇数 的 花snark图 、Petersen 图和 Tietze 图 (Clark and Entringer 1983)。