如果我的问题被重复，请原谅，但我找不到完整的答案来证明所有顶点度数 = 2 的连通图是哈密顿图。
问问题
1325 次
1 回答
1
让给定的图是G。从图中的一个顶点开始，让我们通过重复选择与添加到 的最后一个顶点相邻的顶点来v跟踪任意游走（允许重复顶点的路径），而不重复任何边。如果您无法添加更多顶点或到达之前已经访问过的顶点，则终止。这个过程最终会终止，因为顶点的数量是有限的。请注意，由于每个顶点的度数为 2，因此终止将由顶点重复引起。让这个终止顶点为。我们发现确实是一个包含. 让这个子图只包含这个包含be的循环。设为所有顶点的集合PPtttCV(C)C. 由于所有顶点的度数都2在G和中，因此涉及任何顶点的C每条边都已经在 中。现在，让我们假设有一个 的顶点，比如说，不存在于 中。不会有从到 的任何顶点的路径，因为如果有的话，你最终会得到一条从到外部顶点的边，正如我们刚刚看到的那样，这是不可能的。但是你知道它是连接的，这意味着没有这样的 vertex 。因此，因此只是一个循环。简单地说，它是哈密顿量。GV(C)CGuV(C)uV(C)V(C)GuG = CG
于 2014-12-24T07:30:48.303 回答