2
$\begingroup$

I know the fact, that if a graph is connected and each of its vertices has a degree of $2$, then graph is a cycle graph and it has a Hamiltonian path. From that I easily conclude, that, if graph with n vertices is connected and each of its vertices has a degree at least $2$, then there must be a Hamiltonian cycle in this graph. I dont have a strict mathematical proof of this, but, I think it's obvious from the first fact I mentioned. I can conclude even more : if graph with $n$ vertices is connected and each of its vertices has a degree at least $2$, then this graph must have a subgraph, that is a cycle graph.

The question is, am I thinking correctly?

$\endgroup$
  • $\begingroup$ Brian M. Scott gave a counterexample to your first claim. Your second claim, however, is true, and you don't need connectedness: if each vertex of a finite graph has degree at least $2$, then the graph contains a cycle. Why do you thing containing a cycle is "even more" than having a Hamiltonian cycle? Did you misstate what you were trying to say? $\endgroup$ – bof Nov 3 '13 at 9:56
  • $\begingroup$ Yes, misstating seems like a case here. What I wanted to say with my second claim was actually duplicating a first claim, that is, I was thinking about existance of cycle, that contains all vertices of original graph. $\endgroup$ – Jevgenijs Strigins Nov 3 '13 at 10:22
5
$\begingroup$

What about this graph:

            x       x  
            |\     /|  
            | x---x |  
            |/     \|  
            x       x

It’s connected, and every vertex has degree $2$ or $3$, but there is no Hamilton cycle, thanks to the bridge in the middle.

$\endgroup$
  • $\begingroup$ Thanks for this counterexample. $\endgroup$ – Jevgenijs Strigins Nov 3 '13 at 10:23
  • $\begingroup$ @Jevgenijs: You’re welcome. $\endgroup$ – Brian M. Scott Nov 3 '13 at 10:23

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.