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

Erdős problem #184 · erdosproblems.com/184

Erdos and Gallai conjectured that the edges of every graph on $n$ vertices can be partitioned into $O(n)$ edge-disjoint cycles and single edges; single edges are needed because forests have no cycles, and $K_{3,n-3}$ shows more than $n$ parts may be necessary. Erdos, Goodman and Posa (1966, Section 5) record the problem and an $O(n\log n)$ bound. Conlon, Fox and Sudakov improved this to $O(n\log\log n)$ (2014) and Bucic and Montgomery to $O(n\log^*n)$ ; linear bounds were known for random graphs and graphs of linear minimum degree. Is there an absolute constant $C$ such that every $n$ -vertex graph decomposes into at most $Cn$ cycles and edges?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Extremal graph theory; graph decompositions
Posed by: Paul Erdos and Tibor Gallai, recorded by Erdos, Goodman and Posa (Canad. J. Math. 18, 1966)
Year posed: 1966
Years open: 60y
Solved: 2026-09-24
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 40 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

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.

What the AI did

The release README says every result in openai/math was produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not one of the README's two exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The argument builds on the expansion and path-closing methods of Bucic and Montgomery.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the conjecture and against erdosproblems.com/184; it gives an absolute constant $C$ with every finite simple graph on $n$ vertices partitioned into at most $Cn$ cycles and single edges. Lean: lean/formalization.yaml lists comparator CycleDecomposition with declaration OAI.ErdosGallai.erdos_gallai. The statement ComparatorChallenges/CycleDecomposition.lean was read here: there is a real $C>0$ such that for every $n$ and every SimpleGraph on Fin n there is a $k\le Cn$ and $k$ pairwise disjoint edge sets, each the edge set of a cycle (Walk.IsCycle) or a single edge, whose union is the edge set. This is exactly the headline. Not rebuilt here. Permitted axioms: propext, Quot.sound, Classical.choice.

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

What was actually shown

What the AI did

Verification

Sources

Discussion