MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let us denote the edges incident on vertices of valence 2 as "required" as these edges has to be covered by a Hamiltonian circuit, if one exists on that (undirected) graph. Given a graph on which a proper subset of the "required" edges along with two edges incident on a vertex of valency $\geq 3$ form a cycle, can anything related to the Hamiltonicity of the graph be claimed? A few basic rules for the existence of Hamiltonian Cycles is listed here: Can rule (4) be extended in any way to answer this query?

share|cite|improve this question
This confuses me.. if there is a cycle of "required edges" then surely this is a connected component of the graph which is therefore disconnected and not hamiltonian. – Gordon Royle Nov 8 '10 at 7:26
I share Gordon's confusion. Also, it seems like the title should read: Is this a sufficient condition for a graph to be non-Hamiltonian, and the answer should be yes. – Tony Huynh Nov 8 '10 at 9:33
Sorry.. the cycle is formed by all "required" edges except two. These two are the two edges incident to a vertex of valence $\geq 3$. – Esha Nov 8 '10 at 10:34
Simultaneously crossposted:… – Tsuyoshi Ito Nov 8 '10 at 11:20
cstheory.stackexchange link:… – Esha Nov 9 '10 at 2:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.