Euler and Hamilton circuits with conditions

Euler circuit

A closed walk that uses every edge exactly once. Example: the bowtie with edges ab, bc, ca, cd, de, ec has the Euler circuit c → a → b → c → d → e → c.

   a         d
   |\       /|
   | \     / |
   |  \   /  |
   |   \ /   |
   |    c    |
   |   / \   |
   |  /   \  |
   | /     \ |
   b         e     (edges: ab, ac, bc, cd, ce, de)

(Bowtie: triangles abc and cde sharing vertex c.)

Conditions: a connected graph has an Euler circuit if and only if every vertex has even degree. It has an Euler path (not a circuit) if and only if exactly two vertices have odd degree.

Hamilton circuit

A cycle that visits every vertex exactly once and returns to the start. Example: in the pentagon a–b–c–d–e–a, the circuit a, b, c, d, e, a visits all five vertices.

      a
     / \
    e   b
    |   |
    d---c

Conditions: there is no known simple necessary and sufficient condition.

• Necessary: the graph is connected, every vertex has degree ≥ 2, and it has no cut vertex.
• Sufficient (Dirac): a simple graph with n ≥ 3 vertices in which every vertex has degree ≥ n/2 has a Hamilton circuit.
• Sufficient (Ore): if a simple graph with n ≥ 3 vertices has deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices, it is Hamiltonian.