# Hamilton Path properties

As I understand a graph has a Hamilton Circuit if

• It has $n \ge 3$ vertexes
• degree of every vertex is at least $n/2$
• $\deg u + \deg v \ge n$ for every pair of nonadjacent vertices $u$ and $v$ in the graph

I can't seem to find a concrete set of properties for deciding if a graph has a Hamilton Path. Can anyone help me out? Please add some references/sources :)

-
Note that these conditions are sufficient, but not necessary. A regular hexagon fails the second two, but has a Hamiltonian path. – Ross Millikan Jul 27 '11 at 22:02
You're stating Ore's theorem (but your second condition is not needed): en.wikipedia.org/wiki/Ore_theorem – Justin W Smith Jul 28 '11 at 4:40

A number of sufficient conditions can be found in this thesis of Landon Jennings, among them Chvátal’s condition: if $d_1 \le d_2 \le \dots \le d_n$ are the degrees of $G$, and for $1 \le k \le n/2$ either $d_k \ge k$ or $d_{n+1-k} \ge n-k$, then $G$ has a Hamilton path. The main result of the thesis is the following. Let $G$ be a connected graph with degree sequence $d_1 \le d_2 \le \dots \le d_n$, and let $A(G)$ be the largest integer $k$ such that $\sum\limits_{i=1}^k d_k \le |E(G)|$; if $d_2 \ge A(G)-1$, then $G$ contains a Hamilton path. This test detects some graphs with Hamilton paths not detected by Chvátal’s condition. Some of the references may also be useful.
As stated above, all graphs that contain hamiltonian cycles contain hamiltonian paths, however, this does not capture all graphs that have paths but not cycles. As a simple example consider $P_n$. Also, any connected graph, not isomorphic to $C_n$ where each vertex sits on 1 cycle contains a hamiltonian path but not a hamiltonian cycle. Finally, a connected graph that contains a spanning tree with 2 and only 2 vertices of degree 1 has a hamiltonian path but not a hamiltonian cycle.