How to prove that no hamiltonian cycle exists in the graph

Question

** Show that the graph below has a hamiltonian path but no hamiltonian cycle.

You can find more than one hamiltonian path such as $(b,a,c,f,e,g,d)$. Actually, I tried many times to find a hamiltonian cycle, but I couldn't find a cycle. The problem is how to prove that no hamiltonian cycle exists. I need a logical proof. I can't say "I tried many times but I couldn't find a hamiltonian cycle" because it's not reasonable answer.

Answer 1

Notice that if you delete the edge joining $g$ and $f$, then you get the complete bipartite graph $K_{3,4}$ with sides $\{g,a,f\}$ and $\{b,d,c,e\}$.

It may help now to redraw the graph in the usual way $K_{3,4}$ is drawn. In any case, now you need prove that there is no Hamilton cycle in $K_{3,4}$ and no Hamilton path from $g$ to $f$. Use the fact that the two sides have different number of vertices.

Answer 2

Removing the $3$-subset $\{a,f,g\}$ yields $4$ connected components. Because $3<4$, this subset yields a certificate that the graph does not contain a Hamiltonian cycle.