Lovász Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A graph $G=(V,E)$ is finite, simple and undirected. It is connected if every two vertices are joined by a path. It is vertex-transitive if for every $u,v\in V$ there exists a bijection $\phi:V\to V$ preserving adjacency with $\phi(u)=v$. A Hamiltonian path is an ordering $v_1,\ldots,v_n$ of all $n=|V|$ vertices such that $v_iv_{i+1}\in E$ for $1\le i<n$. A single vertex is itself a Hamiltonian path.

Statement recorded in the supplied source.

Does every nonempty finite connected vertex-transitive graph admit a Hamiltonian path? Explicitly, can one order all its vertices as $v_1,\ldots,v_n$ with every consecutive pair adjacent? The path need not close up to a cycle. [S2]

Short English statement

Can every vertex of a finite connected graph having the same symmetry type at every vertex be visited exactly once along one path?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1329 (GRAPH-005). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Carla Groenland, Sean Longbrake, Raphael Steiner, Jérémie Turcotte and Liana Yepremyan, Longest cycles in vertex-transitive and highly connected graphs (2025), arXiv:2408.04618v2, Section 1, p. 2, formulation of Lovász's 1969 conjecture. https://arxiv.org/abs/2408.04618v2.