# Prove that given graph isn't Hamiltonian

I'm facing the problem of proving that given graph IS NOT Hamiltonian. As far as i know, both Ore's and Durac'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 it's state. Adding a vertex of even degree, with its edges connected to nod-adjacent outer egdes (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.

• What graph do you mean, the one in the picture? Or any graph which has all vertices of degree 3? – cubeception Dec 15 '16 at 19:59
• The one added. Seems like the title isn't exactly concrete, but misleading instead. I will change that. – Mr_Max Dec 15 '16 at 20:02
• Is $S$ a vertex set or an edge set? Or is it both (so you delete a vertex with its edges)? – Ian Dec 15 '16 at 20:22
• S is a vertex set. Of course deleting it deletes also adjacent edges. – Mr_Max Dec 15 '16 at 20:25
• Well, a simple remark is that the graph without the middle vertex is Hamiltonian. So whatever you do you don't want to delete that. – Ian Dec 15 '16 at 20:32