most recent 30 from http://mathoverflow.net 2013-05-25T19:37:11Z http://mathoverflow.net/feeds/question/45272 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45272/necessary-condition-for-a-graph-to-be-non-hamiltonian Esha 2010-11-08T06:52:00Z 2010-11-08T10:36:11Z

<p>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: <a href="http://www.mit.edu/~miforbes/ham_cycle.pdf" rel="nofollow">http://www.mit.edu/~miforbes/ham_cycle.pdf</a> Can rule (4) be extended in any way to answer this query?</p>