0
$\begingroup$

I was asked to draw a Hamilton graph having a Hamilton cycle that traverse an edge more than once.

My first impression of this question was: what? I mean if we are not allowed to visit a vertex more than once doesn't it mean we are not allowed to traverse an edge more than once. But then I thought of the following solution. Consider the graph

G

Then this is a Hamilton graph with a Hamilton cycle $$ v_1,e_1,v_2,e_1,v_1 $$

My question: First, am I right? Can you draw a different Hamilton graph having a Hamilton cycle that traverse an edge more than once? By a different I mean a graph that does not contain the given graph above as its subgraph?

$\endgroup$
  • $\begingroup$ I think you were right the first time. The graph you drew is not a Hamilton cycle because it's not a cycle. Yes, if the definition of "cycle" is formulated carelessly, then that graph might be considered a "cycle", but not if cycle is defined correctly. $\endgroup$ – bof Dec 15 '18 at 7:40
  • $\begingroup$ @bof: So, are implying that there is no such graph? $\endgroup$ – marya Dec 15 '18 at 7:43
  • 1
    $\begingroup$ That would be my answer, but if your textbook's definition of a "cycle" allows a "cycle" with two vertices joined by one edge, you have to go with that. (For me, a cycle with two vertices would also have to have two edges.) What book are you using for graph theory? $\endgroup$ – bof Dec 15 '18 at 7:50

Your Answer

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

Browse other questions tagged or ask your own question.