Is this graph Hamiltonian?

I know that a Hamiltonian graph has a path that visits each vertex once. But I am not sure how to figure out if this one does. Obviously I can try and trace various different paths to see if one works but that is incredibly unreliable.

So my question is, if this graph is Hamiltonian, where would the Hamilton cycle be? And if it is not Hamiltonian, how can we prove it?

Thank you!

Solution 1:

This is a bipartite graph. Colour the three middle vertices red and the other four vertices blue. Each path in the graph has vertices alternating in colour. So any Hamiltonian cycle has an equal number of red and blue vertices...

Solution 2:

A more verbose explanation of the argument made by Lord Shark the Unknown's answer:

This is a bipartite graph (two sets of vertices that form a graph such that no edge places two vertices from the same set adjacent). Colour the three middle vertices red and the other four vertices blue (indicating the two sets).

Every edge in the graph connects a red and a blue vertex. Therefore every path in the graph will visit vertices alternating in color.

Since any cycle has to end on the same vertex as it started, the path has to visit an even number of vertices. Otherwise the path would require connecting a red to a red vertex or a blue to a blue vertex, which we know we cannot do since this is a bipartite graph. This means every cycle will contain an equal amount of red and blue vertices.

Since any Hamiltonian cycle has to contain all vertices and this graph does not have an equal amount of red and blue vertices, it is impossible in this graph to create a Hamiltonian cycle.

Note that the argument does not work the other way around; bipartite graphs exist with equal amounts of points in both sets where Hamiltonian cycles are not possible. Imagine a graph like the one provided in the question, but with four groups of vertices: 2 (red) - 1 (blue) - 1 (red) - 2 (blue). Here it is impossible to create a Hamiltonian cycle since it would require crossing the middle vertices twice.

Solution 3:

One can never trace a Hamiltonian cycle in a graph with vertices having odd egde number. One can never find a Hamiltonian path in a graph with more than two vertices having odd egde number.