Hamilton Cycle Proof Verification Explain why there is no Hamilton cycle in the graph attached below. Then, show that if any pair of non-adjacent vertices in the same graph are joined by an edge, then the resulting graph has a Hamilton cycle. My answers are attached below - would anyone like to compare or give suggestions for my answer? Is it correct?.

My answer:


 A: First off, when you asked to prove that a problem has no solution, showing that an individual candidate solution doesn't work has no value.  So that paragraph should go on stylistic grounds.
Beyond that, you've got two logical problems, and I'll tackle them in the reverse order.


*

*You were asked to show that connecting any two non-adjacent pairs would result in a graph with a Hamilton cycle, and again you only gave one example.  That's fine if every possible way of connecting two non-adjacent vertices is of that form, but you'd have to prove that.  In this case, it is not the only way; you also have to show that connecting 1 and 7 would result in a Hamilton graph.

*You are right in thinking that the fact that $\{2,6,5\}$ is an cut set (sorry, I don't know if "articulation point" is the right phrase when the set is not a singleton -- someone let me know and I'll edit this!) is an important point (although $\{2,6\}$ is all you need).  But you need to go deeper than that, because that would still be a cut set even if you connected 1 and 7, and that graph is Hamiltonian.  The key idea is that removing $2$ and $6$ splits the graph into three components, and that definitely makes the graph non-Hamiltonian.  
So figure that out and write it up prettily, and you'll be all set.
