---
tag: 0HKXNG2RS1
kind: definition
name: Hamiltonian cycle
msc: [05C45]
defines: 0HF30P75G4
uses: [07CT9RDY7Q]
sources:
  - url: https://en.wikipedia.org/wiki/Hamiltonian_path
    locator: Definitions
---

## Definition

Let $G$ be a [[graph|0JD5C82QMB]].
A Hamiltonian cycle of $G$ is a [[cycle|07CT9RDY7Q]] in $G$ that contains every vertex of $G$.

## Remarks

A Hamiltonian path is a [[path|0JDE56HWQ8]] that contains every vertex of $G$.
The names come from William Rowan Hamilton. His icosian game asks for a Hamiltonian cycle on the edges of a dodecahedron.
To decide whether a graph has a Hamiltonian cycle is an NP-complete problem.

## Explanations

### L1 human

A Hamiltonian cycle is a round trip that visits every vertex exactly once.
It is about visiting all vertices, while an Eulerian circuit is about using all edges.