0
$\begingroup$

- Background Information:

I am studying graph theory in discrete mathematics. I have come across Hamilton cycle definition, but there are some things I am not sure about, I need clarification, thanks.


- Definition:

Hamilton Cycle: A path through the graph that starts and ends at the same vertex, and includes all vertices exactly once.


- My Questions:

Considering the last few words,

"[Hamilton cycle] includes all vertices exactly once".

Does this mean that the graph should have only two edges per vertex ?( If you said yes, move on to the graph below, if you said no then explain why).

If you you said yes to my above question, now take a look at this Peterson graph

enter image description here

On chegg.com it says: on removing any vertex(and its incident edges) from the Peterson graph, the resulting sub-graph has a Hamilton cycle. Thus, doing this will result in:

enter image description here

Now we can see that the above graph is a Hamilton cycle, but if you take a closer look now some nodes have degree of 3, such as d(a) = 3 or d(i) = 3.

Summary: I am confused if a Hamilton cycle must have only two edges per vertex or can it have more.

$\endgroup$
1
$\begingroup$

Hamilton Cycle: A path through the graph that starts and ends at the same vertex, and includes all vertices exactly once except the vertex where it starts.

$\endgroup$
  • $\begingroup$ Ok, I understand that, but it is still not clear to me why vertex i, f, d, c, b, and a have degree of 3. It is not only the starting vertex that has a degree of 3. Please explain more why Chegg says why the last graph is a Hamiltonian cycle. $\endgroup$ – Kourosh Feb 2 '18 at 0:12
  • $\begingroup$ I see, can you please clarify this sentence, "[a cycle] that includes all vertices exactly once", doesn't it look like this? ...v1------- v2 ------- v3..., imagine ---- lines are edges and v1,v2,v3 are nodes. $\endgroup$ – Kourosh Feb 2 '18 at 0:23
  • 1
    $\begingroup$ I think you are confused the Hamilton cycle with Euler cycle. The existence of a Hamilton cycle is not related to degrees of vertices. p.s. Euler path visits every edge exactly once. An Euler cycle is an Euler graph which starts and ends on the same vertex and it exists if and only if every vertex of the graph has positive even degree $\endgroup$ – Anson Ng Feb 2 '18 at 0:26
  • $\begingroup$ Yes, you are right, I was confused about the two definitions because different places word the sentence structure differently and it confused me to believe the number of degrees matter, but apparently not. Thanks for your clarification @Anson Ng, +1 :) $\endgroup$ – Kourosh Feb 2 '18 at 0:29

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.