Hamiltonian cycle

A cycle in a graph that visits every vertex exactly once before returning to its starting vertex. Its existence is a central decision problem in graph theory.

Graph theory: The mathematical study of graphs, which consist of vertices connected by edges. Hamiltonian cycles are defined by how edges connect and revisit a graph’s vertices.
Dirac's theorem: A theorem stating that a simple graph with at least three vertices is Hamiltonian if every vertex has degree at least half the number of vertices. It gives a sufficient degree condition guaranteeing a Hamiltonian cycle.
Eulerian cycle: A closed trail in a graph that uses every edge exactly once. It covers edges rather than requiring each vertex to be visited exactly once.
NP-completeness: A complexity classification for decision problems that are both in NP and as hard as every problem in NP. Hamiltonian-cycle existence is NP-complete, making efficient general solutions unlikely.
Path (graph theory): A sequence of distinct vertices in a graph with consecutive vertices joined by edges. A Hamiltonian cycle is a path through every vertex with an added closing edge.
Ore's theorem: A theorem stating that a simple graph with at least three vertices is Hamiltonian if every nonadjacent vertex pair has degree sum at least the number of vertices. It guarantees a cycle through a condition on pairs that lack an edge.
Hamiltonian path: A path in a graph that visits every vertex exactly once, without requiring a return to its start. It drops the closing-edge requirement while retaining the all-vertices condition.
NP: The class of decision problems whose yes answers can be verified in polynomial time given suitable certificates. A proposed Hamiltonian cycle is a certificate that can be checked efficiently.
Cycle (graph theory): A closed path in a graph that begins and ends at the same vertex. The closing return to the starting vertex distinguishes a Hamiltonian cycle from a spanning path.
Bondy–Chvátal theorem: A graph-closure theorem that preserves Hamiltonicity when edges are added between sufficiently high-degree nonadjacent vertices. Its closure operation can turn Hamiltonicity into an easier-to-inspect graph property.

Linked from 6 pages