下面link的图中有哈密尔顿电路吗？

Question

如题中图片所示link.

上图中有hamilton circuit吗？

我发现了一些 hamilton path 比如：

c - b - a -j - i - h -  f - e - d - g

但是没有hamilton circuit

我不能在这里添加图片，因为 Whosebug 不允许我

Answer 1

不可能存在哈密顿循环。

证明：

在哈密顿循环中，必须访问每个顶点，并且不能使用两次边。因此，如果一个顶点的度数为 2，则它的两条边都必须在任何此类循环中使用。

a、c 和 g 是二阶的，因此如果存在哈密顿循环，则它必须包含路径 j - a - b - c - d - g - h。但是，此路径不包含 e，但包含 e 的两个邻居，b 和 d。 e 只剩下一个邻居 f，因此无法将路径扩展到包含 e 的哈密顿循环。因此图中不可能存在哈密顿环。