# Why is G a cycle? Graph G with n vertices, m edges. “(∀v ∈ V(G) : δ(v) = 2 ⇒ G is Hamiltonian) is true because G is a cycle”.

I'm reviewing an earlier exam with solutions by the professor. I found this:

Problem: Let G denote a simple, connected graph with n vertices and m edges. Translate the following statement to English and tell whether it is true or false.

∀v ∈ V(G) : δ(v) = 2 ⇒ G is Hamiltonian.


Solution: If the degree of each vertex is equal to 2, then G is Hamiltonian. True (because G is a cycle).

But how does the professor know that G is a cycle? Couldn't G contain two components? Is it a mistake?

• The text of the exercise states that the graph is connected. – Tom-Tom May 26 '14 at 14:14
• Ah yes you're right. But connected-> cycle? what about graph with V := {a,b,c} and E := {<a,b>,<b,c>}? – user2979713 May 26 '14 at 14:16
• Your example fails because neither $a$ nor $c$ have degree 2. – Jonas May 26 '14 at 14:18
• Yes, you're right. Does degree 2 for all vertices imply cycle? – user2979713 May 26 '14 at 14:19
• Yes. See this question: math.stackexchange.com/questions/390030/… – Jonas May 26 '14 at 14:24

Let $v_0$ be any vertex. Let $v_1$ be one of $v_0$'s neughbours. Then recursively let $v_{k+1}$ be the neighbour of $v_k$ that is not $v_{k-1}$. This sequence is eventually periodic because $G$ is finite. As $v_{k-1}$ is also uniquely determind by $v_k$ and $v_{k+1}$, the sequence is in fact periodic so that we obtain a cycle. Do yo see why this cycle is all of $G$?