Thomassen's conjecture on Hamiltonian vertex-transitive graphs

Status partial high confidence

Thomassen's 1976 conjecture that all but finitely many connected vertex-transitive graphs are Hamiltonian remains open. A series of recent papers has substantially improved the best-known lower bound on the length of longest cycles in connected vertex-transitive graphs on n vertices: from Babai's 1979 bound of Ω(√n) to Ω(n^{13/21}) (2024), then Ω(n^{9/14}) (2025), and most recently n^{2/3−o(1)} (2026). These results make partial progress toward the conjecture but fall far short of establishing Hamiltonicity.

Cited literature (3)

• partial Longest cycles in vertex-transitive and highly connected graphs (2024)
  Groenland, Carla; Longbrake, Sean; Steiner, Raphael; Turcotte, Jérémie; Yepremyan, Liana · arXiv preprint · arXiv:2408.04618

  Proves every connected vertex-transitive graph on n vertices contains a cycle of length Ω(n^{13/21}), improving the previous bound of Ω(n^{3/5}).

• partial Small hitting sets for longest paths and cycles (2025)
  Norin, Sergey; Steiner, Raphael; Thomassé, Stephan; Wollan, Paul · arXiv preprint · arXiv:2505.08634

  Proves every connected vertex-transitive graph of order n contains a cycle (and path) of length Ω(n^{9/14}), improving the Ω(n^{13/21}) bound of Groenland et al.

• partial Towards the Lovász conjecture via sublinear expanders (2026)
  Bucić, Matija; Christoph, Micha; Pokrovskiy, Alexey; Steiner, Raphael · arXiv preprint · arXiv:2606.09742

  Proves every connected vertex-transitive graph of order n contains a cycle of length at least n^{2/3−o(1)}, improving the previous best bound of Ω(n^{9/14}); the authors note this hits a natural barrier for current approaches.

Reviewer notes. The statement reviewed ('All but finitely many connected vertex-transitive graphs are Hamiltonian') is equivalent to Thomassen's 1978 formulation ('sufficiently large connected vertex-transitive graphs are Hamiltonian') referenced in some papers. This is a stronger statement than the related Lovász conjecture (OPG record hamiltonian_paths_and_cycles_in_vertex_transitive_graphs), which only asks for a Hamiltonian path; the Thomassen conjecture asks for a Hamiltonian cycle and is the focus of the three cited partial results. The OPG record hamiltonicity_of_cayley_graphs covers the special case of Cayley graphs, for which better results are known (e.g. abelian groups). A parallel line of work on directed vertex-transitive digraphs (arXiv:2602.16333, arXiv:2607.05807) is not directly relevant to the undirected conjecture reviewed here. The 2026 paper (arXiv:2606.09742) explicitly states its cycle-length bound 'hits a natural barrier for several existing approaches,' suggesting that resolving the full conjecture will require genuinely new techniques.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).