Gallai's Path Decomposition Conjecture

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