# 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?

• Isn't your question answered in these notes you link to? Rule (4) seems to address you question exactly as it is. If there is a non-Hamiltonian cycle formed by required edges, the graph cannot be Hamiltonian. – Karolina Sołtys Nov 8 '10 at 9:39
• crossposted on MO: mathoverflow.net/questions/45272/… – Suresh Venkat Nov 8 '10 at 10:24
• @ Karolina No, it does not. My constraint is " Given a graph on which a PROPER SUBSET of the "required" edges form a cycle" – Esha Nov 8 '10 at 10:29
• @Esha: Regarding crossposting, please see this part of our FAQ. The point is to avoid people on different sites doing double work: meta.cstheory.stackexchange.com/questions/225/… – Aaron Sterling Nov 8 '10 at 14:00
• – Esha Nov 9 '10 at 2:24

If you are satisfied with a heuristic that provides a certificates of non-Hamiltonicity, see Bondy and Murty's book (page 53) for a sufficient, but not necessary, condition for non-Hamiltonicity: If $G$ is Hamiltonian then, for every nonempty subset, $S$, of $V$:
$$\omega(G - S) \le |S|$$
Where $\omega(G - S)$ is the number of connected components left in $G$ after removing the vertices in $S$. A simple counterexample for the converse is the peterson graph: It passes the above test but is not Hamiltonian.