Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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: http://www.mit.edu/~miforbes/ham_cycle.pdf Can rule (4) be extended in any way to answer this query?

share|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: cstheory.stackexchange.com/questions/2777/… –  Tsuyoshi Ito Nov 8 '10 at 11:20
cstheory.stackexchange link: cstheory.stackexchange.com/questions/2777/… –  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.