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.
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.