2
$\begingroup$

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 :)

  • 0
    Note that these conditions are sufficient, but not necessary. A regular hexagon fails the second two, but has a Hamiltonian path.2011-07-27
  • 0
    You're stating Ore's theorem (but your second condition is not needed): http://en.wikipedia.org/wiki/Ore_theorem2011-07-28

3 Answers 3