The Lovász conjecture (in its most widely encountered form) states that without exception, every connectedvertex-transitive
graph is traceable (Lovász 1970; cf.
Gould 1991; Godsil and Royle 2001, p. 45; Mütze 2024).
Amusingly, Babai (1979, 1996) published a directly contradictory conjecture.
While the Lovász conjecture has subsequently been verified for several special orders and classes, both conjectures remain open.
Ma and Zhao (2026) proved a linear lower bound for the graph circumference of every finite connectedvertex-transitive graph. There is an absolute
constant such that every such graph
on vertices contains a graph
cycle of length at least . Moreover, there is an absolute such that, when its vertex
degree is ,
it contains a graph cycle of length at least . This does not establish
either conjecture. Ma and Zhao (2026) report using ChatGPT to explore proof strategies,
develop intermediate claims, and revise the manuscript.
Babai, L. "Automorphism Groups, Isomorphism, Reconstruction." Ch. 27 in Handbook
of Combinatorics, Vol. 2 (Ed. R. L. Graham, M. Grötschel,
M.; and L. Lovász). Cambridge, MA: MIT Press, pp. 1447-1540, 1996.Babai,
L. Problem 17 in "Unsolved Problems." In Summer Research Workshop in
Algebraic Combinatorics. Burnaby, Canada: Simon Fraser University, Jul. 1979.Bermond,
J.-C. "Hamiltonian Graphs." Ch. 6 in Selected
Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson).
London, England: Academic Press, pp. 127-167, 1979.Godsil, C. and
Royle, G. "Hamilton Paths and Cycles." C§3.6 in Algebraic
Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.Gould,
R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th.15,
121-157, 1991.Lovász, L. Problem 11 in "Combinatorial Structures
and Their Applications." In Proc. Calgary Internat. Conf. Calgary, Alberta,
1969. London, England: Gordon and Breach, pp. 243-246, 1970.Ma,
J. and Zhao, Z. "Linear Circumference in Vertex-Transitive Graphs." 1 Oct
2026. https://arxiv.org/abs/2610.02053.Mütze,
T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems."
Not. Amer. Soc.74, 583-592, 2024.
such that every such graph
on 
vertices contains a graph
cycle of length at least 
. Moreover, there is an absolute 
such that, when its vertex
degree is 
,
it contains a graph cycle of length at least 
. This does not establish
either conjecture. Ma and Zhao (2026) report using ChatGPT to explore proof strategies,
develop intermediate claims, and revise the manuscript.
