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$
2
  • $\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
    Commented Nov 3, 2013 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
    Commented Nov 3, 2013 at 10:22

1 Answer 1

Reset to default
6
$\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$
2
  • $\begingroup$ Thanks for this counterexample. $\endgroup$
    – Jevgenijs Strigins
    Commented Nov 3, 2013 at 10:23
  • $\begingroup$ @Jevgenijs: You’re welcome. $\endgroup$
    – Brian M. Scott
    Commented Nov 3, 2013 at 10:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .