The Erdos-Gallai cycle decomposition conjecture (Erdos Problem #184)

Theorem 1.1: an absolute constant $C$ exists such that the edges of every finite simple graph on $n$ vertices partition into at most $Cn$ simple cycles and single edges. Corollary 1.2: every Eulerian graph partitions into at most $Cn$ cycles, and under a quasirandom cut condition into $\Delta/2+\delta n$ cycles. The constant is not computed or optimized; the conjectured sharp values (Erdos suggested $n-1$; $K_{3,n-3}$-type lower bounds of about $3n/2$) are not addressed.

Theorem 1.1: an absolute constant $C$ exists such that the edges of every finite simple graph on $n$ vertices partition into at most $Cn$ simple cycles and single edges. Corollary 1.2: every Eulerian graph partitions into at most $Cn$ cycles, and under a quasirandom cut condition into $\Delta/2+\delta n$ cycles. The constant is not computed or optimized; the conjectured sharp values (Erdos suggested $n-1$; $K_{3,n-3}$-type lower bounds of about $3n/2$) are not addressed.