Show that a graph has no hamiltonian cycle

Question

I'm sorta good at finding hamiltonian cycle, but showing that a graph doesn't have one is beyond me.

Answer 1

A pretty useful necessary condition for the existence of a Hamiltonian cycle is the following result:

Proposition. If $G$ is a Hamiltonian graph, then deleting any $k$ vertices from $G$ results in a graph with at most $k$ connected components.

This holds because it's true for the cycle graph $C_n$: deleting $k$ vertices from the cycle graph results in $k$ paths, or possibly fewer paths if any of the deleted vertices were adjacent. A Hamiltonian graph is just a cycle graph with some more edges added on, and the extra edges can only reduce the number of components.

This is not a universal test for Hamiltonicity: that would be too much to hope for. However, in many cases, we can use this result to show that a graph is not Hamiltonian. In your example, we can find $5$ vertices whose removal leaves the graph in $6$ connected components, proving that it cannot have a Hamiltonian cycle.