关于判断图G是否为哈密顿图的技术问询

问题描述 #

我有一个图$G$，它的结构是：两个独立的三角形子图，通过一条包含两个中间顶点的路径相连——路径的一端连接左边三角形的一个顶点，另一端连接右边三角形的一个顶点。我认为这个图是非哈密顿图，但一直找不到验证的方法。我知道哈密顿图的一个必要判定规则：如果存在正整数$n$，从图中移除$n$个顶点后，得到的子图连通分支数大于$n$，那么该图一定不是哈密顿图，但我始终没找到满足这个条件的顶点集合。

专家解答 #

嘿，我来给你理清楚这个问题~ 你提到的那个顶点割判定规则确实是验证非哈密顿图的利器，只是你可能没找对顶点集合：

• 精准定位符合条件的顶点割：你可以试试移除连接中间路径与两个三角形的那两个顶点（也就是左边三角形和中间路径相连的顶点，加上右边三角形和中间路径相连的顶点）。移除这2个顶点后，原图会被拆成3个完全独立的连通分支：左边三角形剩下的2个顶点、中间路径的2个顶点、右边三角形剩下的2个顶点。这时候$n=2$，连通分支数是3，显然3>2，完全符合你知道的那个必要判定条件，直接就能证明这个图是非哈密顿图啦！

• 备用思路：反证法推导矛盾：如果刚才的顶点割你没找到，也可以用反证法试试。先假设这个图存在哈密顿回路，那这个回路必须经过所有8个顶点。你顺着中间路径走的话，从左边三角形到中间路径再到右边三角形，要是想形成闭合回路，必然得从右边三角形绕回左边，但你会发现，移除那两个连接顶点后分支都断开了，回路根本没法跨分支连接，这就和存在哈密顿回路的假设矛盾了，也能证明它是非哈密顿图。

备注：内容来源于stack exchange，提问作者J. Ross