下面的链接中是否有哈密尔顿电路图？

Question

像链接中的图像中说的问题。

上图中是否有hamilton circuit？

我发现了一些hamilton path像：

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

但没有hamilton circuit

我不能在这里添加的图片，因为计算器didnt让我

Answer 1

不能有一个汉密尔顿周期。

证明：

在汉密尔顿的周期，每个顶点必须被访问，没有边缘可以使用两次。因此，如果一个顶点具有二阶，那么它的两个边必须在任何这样的循环中使用。

a,c和g是二级，所以如果存在哈密尔顿循环，它必须包含路径j - a - b - c - d - g - h。但是，此路径不包含e，但它包含两个e的邻居，b和d。 e只有一个剩余的邻居f，因此无法将路径扩展到包含e的哈密尔顿循环。因此图中不会出现哈密尔顿循环。