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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Asking whether a graph is non-Hamiltonian is CoNP-Complete so it is doubtful that such an algorithm exists.
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.