Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do I prove that the following graph is a non-Hamiltonian cycle?

$\hspace{5.3cm}$enter image description here

I'm asked to create a graph which is both non-Eulerian and non-Hamiltonian, and this is what I produced in TiKz. My approach is the following:


Here it is clear that the graph has no Eulerian cycle as $\text{deg}(v_1)=\text{deg}(v_2)=\text{deg}(v_3)=3$, which is odd. Also, the graph is not Hamiltonian since if we start at $v_5$, then no matter what path is taken the tracing must lead back to $v_5$, but this cannot be done as one would be traversing $e_7$ twice. Furthermore, for any other starting vertex a Hamiltonian cycle must hit all vertices, so when the path arrives at $v_5$ the tracing must go back across $e_7$, and so this would not count.


Here, a "cycle" is a no-repeated-edge cycle...


share|improve this question

2 Answers 2

up vote 2 down vote accepted

I agree. Your graph is neither Eulerian nor has it a Hamiltonian cycle (By the way, you should check your wording, a graph is either non-Hamiltionian or has no Hamiltonian cycles, but being a non-Hamiltonian cycle implies that the graph is a cycle itself)

Are you sure, that there is no other condition on your graph? (Maybe something like $2$-connectedness?) It is obvious that, a graph with a vertex of degree one, is never Eulerian or Hamiltonian, so

. _ .

is an even simpler counter-example.

share|improve this answer

This seems generally O.K. However, I do have two remarks.

First, "graph is a non-Hamiltonian cycle" would mean that "graph is a cycle (which is almost meaningless in itself), but not Hamiltonian". It would be better to say that the "graph doesn't have a Hamiltonian cycle".

Second, since a cycle goes around, you can always pick the "starting" vertex, so there is no need to observe the case "for any other starting vertex"; it's enough to show that there is no cycle "starting" from $v_5$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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