discrete-mathematics - 下面链接的图中是否有哈密顿回路？

Question

就像问题在链接中的图片中所说的那样。

hamilton circuit上图中有a吗？

我发现了一些hamilton path像：

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

但不是hamilton circuit

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

Answer 1

不可能有哈密顿循环。

证明：

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

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