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?

Take the 2-minute tour
×

MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

sufficientcondition for a graph to be non-Hamiltonian, and the answer should beyes. – Tony Huynh Nov 8 '10 at 9:33