Lovász Conjecture

The Lovász conjecture (in its most widely encountered form) states that without exception, every connected vertex-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.

A similar conjecture attributed to Thomassen (Bermond 1979, Gould 1991) asserts that, with exactly five exceptions (the nonhamiltonian vertex-transitive graph), every vertex-transitive graph is Hamiltonian.

See also

Hamiltonian Cycle, Hamiltonian Graph, Hamiltonian Path, Nonhamiltonian Vertex-Transitive Graph, Traceable Graph, Vertex-Transitive Graph

Explore with Wolfram|Alpha


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.

Cite this as:

Weisstein, Eric W. "Lovász Conjecture." From MathWorld--A Wolfram Web Resource.

Subject classifications