TOPICS
Search

Gallai's Path Decomposition Conjecture


Gallai's path decomposition conjecture asserts that if G is a finite connected simple graph on n vertices, then its edges can be partitioned into at most [n/2] simple paths, where [x] is the ceiling function (Lovász 1968, Chu et al. 2026). The paths may share vertices, but each graph edge must belong to exactly one of them.

The conjecture remains open in general (Chu et al. 2026). Its requirement of paths is stronger than allowing both paths and cycles in the partition.

This is problem 583 in the Erdős problems collection (Bloom 2026).

A random-graph special case admits the stronger odd-degree lower bound. Lin and Yang (2026) proved that, when p=o(1) and np/lnn->infty, the random graph G(n,p) has with high probability an edge decomposition into nonempty simple paths whose number is half the number of odd-degree vertices. Here o denotes little-o notation.


See also

Erdős Problems, Graph Path

Explore with Wolfram|Alpha

References

Bloom, T. F. "Erdős Problem 583." Accessed Oct. 26, 2026. https://www.erdosproblems.com/583.Chu, Y.; Fan, G.; and Zhou, C. "Gallai's Conjecture and the Path Number of Odd Semi-Cliques." Disc. Math. 349, 114725, 2026. https://doi.org/10.1016/j.disc.2025.114725.Lin, J. and Yang, H. "Optimal Path Decompositions of Sparse Random Graphs." 27 Oct 2026. https://arxiv.org/abs/2610.37173.Lovász, L. "On Covering of Graphs." In Theory of Graphs (Proc. Colloq., Tihany, 1966) (Ed. P. Erdős and G. Katona). New York: Academic Press, pp. 231-236, 1968.

Cite this as:

Weisstein, Eric W. "Gallai's Path Decomposition Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GallaisPathDecompositionConjecture.html

Subject classifications