证明有度连通图= 2的哈密顿圈 [英] prove connected graph with degree = 2 has hamiltonian cycle

问题描述

原谅我，如果我的问题是重复的，但我找不到一个完整的答案，证明一个连通图，所有的顶点有度= 2是一个Hamilton图。

excuse me if my question is repeated but i couldn't find a complete answer to prove that a connected graph which all vertices has degree = 2 is a hamiltonian graph.

我读<一href="http://math.stackexchange.com/questions/494091/how-do-i-prove-that-a-graph-if-hamiltonian-it-must-be-2-connected">this和<一href="http://math.stackexchange.com/questions/278520/is-this-graph-g-2-connected-and-non-hamiltonian-does-fleischners-theorem-app">this

推荐答案

让给定的图形是。从图中的一个顶点 v 开始，让我们跟踪（与允许重复顶点的路径）， P 任意散步，通过反复挑选一个顶点相邻的最后一个顶点加入 P ，没有任何重复的边缘。终止，如果你不能添加任何更多的顶点，或者如果你达到一个已经访问过一个顶点。这一过程将最终终止，因为有有限个顶点。请注意，由于每个顶点有度二，终止将由一个顶点重复造成的。让这终止顶点是 T 。我们发现确实含有周期 T 。让这个子图由眼前这个周期包含 T 的是 C 。让 V（C）是集 C 所有顶点。由于所有的顶点有度 2 和 C 在每边有任何的顶点在 V（C）已经在 ç。现在，让我们假设有的顶点，说 U ，而不是present在 V（C）。这里将是任何一个顶点没有从 U 路径 V（C），因为如果有一个，你会结束了与 V（C）的边缘去一个顶点外，正如我们刚才看到的是不可能的。但是，你知道，连接，这意味着没有这样的顶点 U 。因此，，因此只是一个循环。平凡，这是汉密尔顿。

Let the given graph be G. Starting from a vertex v in the graph, let us trace an arbitrary walk(path with repeated vertices allowed), P, by repeatedly picking a vertex adjacent to the last vertex added to P, without repeated any edges. Terminate if you cannot add any more vertices or if you reach a vertex that was already visited before. This process will eventually terminate since there are finitely many vertices. Note that since every vertex has degree two, the termination will be caused by a vertex repeating. Let this termination vertex be t. What we have found is really a cycle containing t. Let this subgraph consisting of just this cycle containing t be C. Let V(C) be the set of all vertices of C. Since all the vertices have degree 2 in G and C, every edge in G involving any of the vertices in V(C) is already in C. Now, let us suppose there is a vertex of G, say u, not present in V(C). There will be no path from u to any vertex of V(C), because if there was one, you would end up with an edge going from V(C) to a vertex outside, which as we just saw isn't possible. But you know that G is connected, implying that there is no such vertex u. Thus, G = C and hence G is just a cycle. Trivially, it is Hamiltonian.

这篇关于证明有度连通图= 2的哈密顿圈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！