non-Hamiltonian Cycles: How to Prove for Small Graphs

Question

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

$\hspace{5.3cm}$

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

---

Answer 1

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.

Answer 2

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