Lovász conjecture

The Lovász conjecture states that every finite connected vertex-transitive graph has a Hamiltonian path. It remains open in general.

Connect

Vertex-transitive graph: A graph whose automorphism group acts transitively on its vertices. Vertex-transitivity is the symmetry condition imposed on every graph in the conjecture.
Petersen graph: A ten-vertex cubic graph that is vertex-transitive but has no Hamiltonian cycle. It satisfies the conjecture through Hamiltonian paths despite lacking a Hamiltonian cycle.
László Lovász: A Hungarian mathematician whose work spans combinatorics, graph theory, and theoretical computer science. Lovász posed the problem that became the conjecture bearing his name.
Hamiltonian-connected graph: A graph in which every pair of distinct vertices is joined by a Hamiltonian path. The conjecture asks for one Hamiltonian path, not one between every vertex pair.
Hamiltonian path: A path that visits every vertex of a graph exactly once. This is the spanning structure the conjecture predicts.
Dodecahedral graph: The graph whose vertices and edges are the corners and edges of a regular dodecahedron. Its vertex-transitivity and Hamiltonian cycle provide a concrete affirmative case.
Tutte conjecture: The conjecture that every 3-connected planar graph has a Hamiltonian cycle. Its stronger cycle claim is a related conjecture about Hamiltonicity, not vertex-transitivity.
Traceable graph: A graph that contains at least one Hamiltonian path. The conjecture says every graph in its specified class is traceable.
Connected graph: A graph in which every pair of vertices is joined by a path. The conjecture excludes disconnected graphs, where one spanning path cannot exist.
Complete graph: A simple graph in which every pair of distinct vertices is adjacent. Every complete graph with at least two vertices has a Hamiltonian path.