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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.