I'm facing the problem of proving that given graph IS NOT Hamiltonian. As far as I know, both Ore's and Dirac's theorem do not work in opposite direction. Therefore I'm left with another "hint" given on lecture, stating:
- If $G\setminus S$ yields more than $|S|$ components, it is not Hamiltonian.
I haven't found any such subset. I've seen solutions to such problems, however containing a bridge, which isn't the case here. I do also know that obviously from every vertex of degree $2$ both of its edges must be used. However I do not know how to use this knowledge here. Could you show me how to use the tools I have or which way to follow here?
EDIT 1: If we start constructing given graph from the outer circle, without adding any inner edges or vertex K, we have a graph that is Hamiltonian. In this case, adding any edge doesn't change its state. Adding a vertex of even degree, with its edges connected to non-adjacent outer edges (for example here K connected with B and E, not B and A) seems to make it non-Hamiltonian. Although it seems to also work here, I can't figure out a formal explanation.
PS. Thank you Brian for editing.
The Petersen graph is well-known to be non-Hamiltonian. This graph is a spanning subgraph of the Petersen graph obtained by edge deletion. Thus it is non-Hamiltonian.