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).
Kim (2026) reports substantial mathematical assistance from ChatGPT and Claude in developing the proof.
