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