<p>Asking whether a graph is non-Hamiltonian is CoNP-Complete so it is doubtful that such an algorithm exists.</p>

<p>If you are satisfied with a heuristic that provides a certificates of non-Hamiltonicity, see <a href="http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/pdf/chapter4.pdf" rel="nofollow">Bondy and Murty's</a> <a href="http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html" rel="nofollow">book</a> (page 53) for a sufficient, but not necessary, condition for non-Hamiltonicity:  If $G$ is Hamiltonian then, for every nonempty subset, $S$, of $V$:</p>

<p>$$ \omega(G - S) \le |S| $$</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Petersen_graph" rel="nofollow">peterson graph</a>: It passes the above test but is not Hamiltonian.</p>

CC BY-SA 2.5
2011-01-10T09:22:48.900Z
I don't believe that CoNP-complete is significant here. The reason is that the property cannot be used as a certificate, since it cannot be applied to any graph. It may be possible that Non-Hamiltonicity is in P for this restricted family of inputs.
chazisop
CC BY-SA 2.5
2011-01-10T03:39:28.907Z
2011-01-10T03:39:28.907Z
user834
<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>

CC BY-SA 2.5
2010-11-08T14:00:14.103Z
@Esha: Regarding crossposting, please see this part of our FAQ.  The point is to avoid people on different sites doing double work: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231
Aaron Sterling
CC BY-SA 2.5
2010-11-08T15:43:33.420Z
Ok.. Thanks and sorry about this. Won't do it in future.
Esha
CC BY-SA 2.5
2010-11-08T15:51:01.980Z
@Esha: the easiest is to include all other urls where you have posted the same question. Secondly, if this or your previous postings is homework or some project you're doing, I also think it is good style to reference the cstheory discussions where you got valuable information from.
Michael
CC BY-SA 2.5
2010-11-09T02:24:43.963Z
MO Link: http://mathoverflow.net/questions/45272/necessary-condition-for-a-graph-to-be-non-hamiltonian
Esha
CC BY-SA 2.5
2010-11-08T09:39:58.357Z
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
CC BY-SA 2.5
2010-11-08T10:24:31.200Z
crossposted on MO: http://mathoverflow.net/questions/45272/necessary-condition-for-a-graph-to-be-non-hamiltonian
Suresh Venkat
CC BY-SA 2.5
2010-11-08T10:29:38.670Z
@ Karolina No, it does not. My constraint is " Given a graph on which a PROPER SUBSET of the "required" edges form a cycle"
Esha
CC BY-SA 2.5
2010-11-08T11:01:51.393Z
Ok, but that still means, that the graph cannot be Hamitonian - you use rule (5), which gives you some non-Hamiltonian cycle of vertices of degree 2, and you have to use all edges of it.
Karolina Sołtys
CC BY-SA 2.5
2010-11-08T13:34:16.577Z
@ Suresh Venkat : Is crossposting not allowed?
Esha
<graph-theory><co.combinatorics>
Necessary condition for a graph to be Non-Hamiltonian
Esha
# Necessary condition for a graph to be Non-Hamiltonian

(Asked by: username_0 on 2010-11-08)

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?

**Tags:** graph-theory, co.combinatorics
> **Comments:**
> **username_3**: 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.  
> **username_4**: crossposted on MO: http://mathoverflow.net/questions/45272/necessary-condition-for-a-graph-to-be-non-hamiltonian  
> **username_0**: @ Karolina No, it does not. My constraint is " Given a graph on which a PROPER SUBSET of the "required" edges form a cycle"  
> **username_3**: Ok, but that still means, that the graph cannot be Hamitonian - you use rule (5), which gives you some non-Hamiltonian cycle of vertices of degree 2, and you have to use all edges of it.  
> **username_0**: @ Suresh Venkat : Is crossposting not allowed?  
> **username_1**: @Esha: Regarding crossposting, please see this part of our FAQ.  The point is to avoid people on different sites doing double work: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231  
> **username_0**: Ok.. Thanks and sorry about this. Won't do it in future.  
> **username_2**: @Esha: the easiest is to include all other urls where you have posted the same question. Secondly, if this or your previous postings is homework or some project you're doing, I also think it is good style to reference the cstheory discussions where you got valuable information from.  
> **username_0**: MO Link: http://mathoverflow.net/questions/45272/necessary-condition-for-a-graph-to-be-non-hamiltonian  

---

## 1 answers

### Answer by username_5 on 2011-01-10. Score: 1

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](http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/pdf/chapter4.pdf) [book](http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html) (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](http://en.wikipedia.org/wiki/Petersen_graph): It passes the above test but is not Hamiltonian.

> **Comments:**
> **username_6**: I don't believe that CoNP-complete is significant here. The reason is that the property cannot be used as a certificate, since it cannot be applied to any graph. It may be possible that Non-Hamiltonicity is in P for this restricted family of inputs.  

---

