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?

enter image description 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.

  • $\begingroup$ What graph do you mean, the one in the picture? Or any graph which has all vertices of degree 3? $\endgroup$ – cubeception Dec 15 '16 at 19:59
  • $\begingroup$ The one added. Seems like the title isn't exactly concrete, but misleading instead. I will change that. $\endgroup$ – Mr_Max Dec 15 '16 at 20:02
  • $\begingroup$ Is $S$ a vertex set or an edge set? Or is it both (so you delete a vertex with its edges)? $\endgroup$ – Ian Dec 15 '16 at 20:22
  • $\begingroup$ S is a vertex set. Of course deleting it deletes also adjacent edges. $\endgroup$ – Mr_Max Dec 15 '16 at 20:25
  • $\begingroup$ 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. $\endgroup$ – Ian Dec 15 '16 at 20:32

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. enter image description here

  • $\begingroup$ The peterson graph is connected and not a tree, and therefore contains a cycle. Are you implying that such a cycle which is a proper subgraph of the peterson graph is non-hamiltonion? $\endgroup$ – JMoravitz Dec 15 '16 at 20:36
  • 3
    $\begingroup$ This graph is obtained from the Petersen graph by deleting only edges, so if the Petersen graph is not Hamiltonian, then this graph isn't Hamiltonian. $\endgroup$ – D. Thomine Dec 15 '16 at 20:39
  • $\begingroup$ @D.Thomine Now that is a good and correct argument. Now if Laars would correct his post I could remove the downvote, because as worded it is incorrect. A proper subgraph obtained only by deleting edges is a very different concept than simply a proper subgraph. $\endgroup$ – JMoravitz Dec 15 '16 at 20:43
  • $\begingroup$ @JMoravitz, I agree, that's why I'm waiting before I can upvote this answer. I just found useful to point the correct version of the argument. $\endgroup$ – D. Thomine Dec 15 '16 at 20:44
  • $\begingroup$ Fixed. I was trying to draw a picture and get it added to this post. I should have taken more time to read what I posted. $\endgroup$ – Laars Helenius Dec 15 '16 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.