# Necessary condition for a graph to be Non-Hamiltonian

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?

-
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