Let G be a simple undirected graph.

If G is connected, and every vertex has degree $2$, then G is hamiltonian. (In fact, G only consists of the hamilton-circle)

Are there some weaker sufficient conditions for G being hamiltonian, if G is $2$-connected ? I am particular interested in the case, where all the degrees of the vertices are $2$ or $3$.

It would also be great, if someone knows necessary conditions for a $2$-connected graph to be hamiltonian.

With hamiltonian it is meant that G has a hamilton-circle, not just a hamilton-path.

  • $\begingroup$ 2-connectedness is itself a necessary condition for a graph to be Hamiltonian. So actually, the question is asking for necessary conditions for Hamiltonicity - which I'm sure you can find answers for on google scholar (though we really don't know much). I don't know if there are results on graphs with degrees 2 and 3, but if all vertices are degree 3, then this question relates to Tait's conjecture : en.wikipedia.org/wiki/Tait's_conjecture (though the graph must be 3-connected). $\endgroup$ – Manuel Lafond Sep 1 '14 at 18:12
  • $\begingroup$ Shouldnt there be a hamiltonian cycle iff there is a perfect matching on the subgraph of vertices with degree 3. Because if you delete the matching you get the case with every vertex degree 2 and connected and if you have a hamiltonian cycle and delete it then you get a perfect matching on the degree 3 vertices. $\endgroup$ – mathdotrandom Oct 24 '17 at 12:05

Your Answer

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

Browse other questions tagged or ask your own question.