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?

  • $\begingroup$ 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. $\endgroup$ – Gordon Royle Nov 8 '10 at 7:26
  • $\begingroup$ 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. $\endgroup$ – Tony Huynh Nov 8 '10 at 9:33
  • $\begingroup$ 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$. $\endgroup$ – Esha Nov 8 '10 at 10:34
  • 1
    $\begingroup$ Simultaneously crossposted: cstheory.stackexchange.com/questions/2777/… $\endgroup$ – Tsuyoshi Ito Nov 8 '10 at 11:20
  • 1
    $\begingroup$ cstheory.stackexchange link: cstheory.stackexchange.com/questions/2777/… $\endgroup$ – Esha Nov 9 '10 at 2:25

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.