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.
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.
