Hamiltonian Path Detection

Question

Are there any special things to check to determine if a graph does not have a Hamiltonian Path. I know for a Euler Path you can check to see if there are any odd degrees or if the graph is disconnected. Are there any rules like that for Hamiltonian Paths?

Answer 1

As mentioned in the other answer by Gerry Myerson, there is no simple neccessary and sufficient condition, since the problem of determining if a general graph has a Hamiltonian Path is NP-complete. But as he also states, there are both nice sufficient conditions, and nice necessary conditions.

You mention yourself, that connectedness is a necessary condition for having an Eulerian trail, and this is of course also a necessary condition for having a Hamilton path. If you want to guarantee a Hamilton cycle, you need 2-connectivity.

Another simple necessary condition for having a Hamilton path, is that there can be at most 2 vertices of degree 1.

This article, describes a sufficient condition, which states that for a graph $G$, if the degree sum of all pairwise nonadjacent vertex-triples is greater than $\frac{1}{2}(3n - 5)$, then $G$ has a Hamilton path.

Here is a number of sufficient conditions for having Hamiltonian cycles, which is of course also sufficient for a having a Hamiltonian path.

A Theorem of Dirac states that: If $G$ is a simple graph with $n$ vertices where $n \geq 3$ and $\delta(G) \geq n/2$, then $G$ is Hamiltonian, where $\delta(G)$ denotes the minimum degree of $V(G)$.

Another sufficient condition by Ore states that: If $d(u) + d(v) \geq n$ for every pair of distinct nonadjacent vertices $u$ and $v$ of $G$, then $G$ is Hamiltonian.

A lot of sufficient conditions for Hamiltonian graphs are surveyed here.

Answer 2

There are some simple necessary conditions, and some simple sufficient conditions, but there is no simple necessary and sufficient condition, the way there is for the Eulerian question. Have you had a look at Wikipedia?

Answer 3

"If G is a simple graph with n vertices and each vertex in G has at least ⌈n/2⌉ neighbors, then G is Hamiltonian" DIRAC's THEOREM