Gallai's path decomposition conjecture asserts that if is a finite connected simple graph on
vertices, then its edges
can be partitioned into at most
simple paths, where
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 and
,
the random graph
has with high probability an edge decomposition into
nonempty simple paths whose number is half the number
of odd-degree vertices. Here
denotes little-o notation.