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.
Babai, L. Problem 17 in "Unsolved Problems." In Summer Research Workshop in Algebraic Combinatorics. Burnaby, Canada: Simon
Fraser University, Jul. 1979.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.Bermond,
J.-C. "Hamiltonian Graphs." Ch. 6 in Selected
Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson).
London: 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: Gordon and Breach, pp. 243-246, 1970.Mütze,
T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems."
Not. Amer. Soc.74, 583-592, 2024.
