Short note: Hamiltonian graph

A Hamiltonian circuit in a graph is a simple cycle that passes through every vertex exactly once; a graph containing one is a Hamiltonian graph. A Hamiltonian path visits every vertex once but need not return to the start. The name comes from Sir W. R. Hamilton's "Icosian game" (a tour of the dodecahedron's vertices).

Examples: every cycle Cₙ, the complete graph Kₙ (n ≥ 3) and the cube Q₃ are Hamiltonian. K₂,₃ and the Petersen graph are not.

      a
     / \
    e   b      Hamiltonian circuit: a, b, c, d, e, a
    |   |
    d---c

Conditions: no simple necessary and sufficient condition is known (deciding whether a graph is Hamiltonian is an NP-complete problem).

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

Difference from Euler: Hamilton concerns vertices; Euler concerns edges.

Application: the travelling salesman problem asks for the cheapest Hamiltonian circuit in a weighted complete graph.