TOPICS
Search

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.

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.

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 connected vertex-transitive graph. There is an absolute constant c>0 such that every such graph on n>=3 vertices contains a graph cycle of length at least cn. Moreover, there is an absolute d_0 such that, when its vertex degree is d>=d_0, it contains a graph cycle of length at least (1-d^(-1/100))n. This does not establish either conjecture. Ma and Zhao (2026) report that the ball-growth dichotomy used in their proof emerged from discussions with ChatGPT.

See also

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

Explore with Wolfram|Alpha

References

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. Math. Soc. 71, 583-592, 2024. https://doi.org/10.1090/noti2907.

Referenced on Wolfram|Alpha

Lovász Conjecture

Cite this as:

Weisstein, Eric W. "Lovász Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LovaszConjecture.html

Subject classifications