<p>Your question is kind of vague, and I don't know of a comprehensive listing of necessary conditions for Hamiltonicity (or equivalently sufficient conditions for non-Hamiltonicity). But for one such condition, commonly used to prove non-Hamiltonicity of certain planar graphs, see <a href="https://en.wikipedia.org/wiki/Grinberg%27s_theorem">Grinberg's theorem</a>.</p>

<p>Another necessary condition, valid for all graphs (not just planar graphs), is that a Hamiltonian graph must be <a href="https://en.wikipedia.org/wiki/Graph_toughness">1-tough</a>. So if you can find a set of $k$ vertices whose removal disconnects the remaining graph into more than $k$ pieces, it's not Hamiltonian.</p>

CC BY-SA 3.0
2015-08-22T09:03:25.847Z
Thanks david, i now realise that the condition i thought about was already found and it is exactly what you mentioned in your answer about 1-toughness. nice!
Ofek Ron
CC BY-SA 3.0
2015-08-22T01:07:06.457Z
2015-08-22T04:35:51.973Z
2015-08-22T04:35:51.973Z
David Eppstein
<p>I think i have a sufficient condition for non existance of hamiltonian cycle in a graph, I want to check if it has already been found, I tried googling for it and didnt find anything so far, how can i go about finding out if this condition is new?</p>

CC BY-SA 3.0
2015-08-22T02:23:39.727Z
You could write what it is in this post so that people on here could help....
usul
<graph-theory><hamiltonian-paths>
A sufficient condition for non existance of hamiltonian cycle
Ofek Ron
# A sufficient condition for non existance of hamiltonian cycle

(Asked by: username_0 on 2015-08-22)

I think i have a sufficient condition for non existance of hamiltonian cycle in a graph, I want to check if it has already been found, I tried googling for it and didnt find anything so far, how can i go about finding out if this condition is new?

**Tags:** graph-theory, hamiltonian-paths
> **Comments:**
> **username_1**: You could write what it is in this post so that people on here could help....  

---

## 1 answers

### Answer by username_2 on 2015-08-22. Score: 8 | Accepted answer

Your question is kind of vague, and I don't know of a comprehensive listing of necessary conditions for Hamiltonicity (or equivalently sufficient conditions for non-Hamiltonicity). But for one such condition, commonly used to prove non-Hamiltonicity of certain planar graphs, see [Grinberg's theorem](https://en.wikipedia.org/wiki/Grinberg%27s_theorem).

Another necessary condition, valid for all graphs (not just planar graphs), is that a Hamiltonian graph must be [1-tough](https://en.wikipedia.org/wiki/Graph_toughness). So if you can find a set of $k$ vertices whose removal disconnects the remaining graph into more than $k$ pieces, it's not Hamiltonian.

> **Comments:**
> **username_0**: Thanks david, i now realise that the condition i thought about was already found and it is exactly what you mentioned in your answer about 1-toughness. nice!  

---

