Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

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?

share|improve this answer
2  
In particular, the computational problem of determining whether a graph has a Hamilton path is NP-Complete. –  Thomas Andrews Apr 11 '12 at 13:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.