Math Conjectures

Lovász Hamiltonian-Path Conjecture

OPENLandmarkConjectureProposed 1969 · Standard version

Canonical statement

Every finite connected vertex-transitive graph has a Hamiltonian path. A graph is vertex-transitive if, for every two vertices u,vu,v, it has an automorphism sending uu to vv; a Hamiltonian path visits every vertex exactly once.
View source LaTeX
Every finite connected vertex-transitive graph has a
Hamiltonian path. A graph is vertex-transitive if, for every two vertices
\(u,v\), it has an automorphism sending \(u\) to \(v\); a Hamiltonian
path visits every vertex exactly once.
GRAPH-026:[Lovasz1969ProblemSession][Babai1979LongCycles][BucicEtAl2026Lovasz]
Graph theoryCombinatorics

Notes

Long paths and cycles are guaranteed in every connected vertex-transitive graph, with substantially improved bounds in 2026, but no argument forces a spanning path and no counterexample is known.
This record uses the standard Hamiltonian-path formulation. Stronger Hamiltonian-cycle statements require explicit exceptional graphs and are not equivalent.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.