The Erdős-Gallai cycle decomposition conjecture asserts that the edges of every simple
graph on 
vertices can be partitioned
into at most 
cycles and individual edges,
for an absolute constant 
.
Equivalently, every simple graph on 
vertices in which every vertex degree is even
has a partition of its edges into at most 
cycles (Kim 2026).
Kim (2026) reported a proof. The conjecture is problem 184 in the Erdős problems collection (Bloom 2026).
