Problem 184

Any graph on $n$ vertices can be decomposed into $O(n)$ many edge-disjoint cycles and edges.

Graph theory
Cycles

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

OPEN, the site's label (page last edited 1 April 2026; proof-claim tab read 2026-10-07); the derived standing of this page is solved, proved. The two differ because the standing rests on a theorem the label does not reflect: the site's page was last edited before either 2026 claim, and the release's theorem below is not on the site's proof-claim tab. Theorem 1.1 of the OpenAI mathematics release's preprint of 24 September 2026 gives an absolute $C$ with $f(n)\le Cn$ for every $n$ . It is recorded on its claim page (OpenAI, 2026) as accepted, with evidence formalized only: the corpus's verification of 2026-10-07 built the release's Lean declarations OAI.ErdosGallai.erdos_gallai, MainStatement, EdgeDecomposition and CycleOrSingleEdge at the pinned revision, found exactly the axioms propext, Classical.choice and Quot.sound, and audited the formal statement for fidelity to the question, an audit that belongs to that evidence and is not an outside review; no outside reviewer is recorded, the informal manuscript is unrefereed and its proof was read for structure only. A second full claim, Ryan Coffey's Lean-formalized proof of the formal-conjectures statement (1 October 2026), is recorded as claimed on its claim page (Coffey, 2026). Before these, the best upper bound in the refereed record was Bucić and Montgomery's Theorem 2, $f(n)=O(n\log^\star n)$ with $\log^\star$ the iterated logarithm (Adv. Math. 437 (2024), refereed; cited from the arXiv v2), after Conlon, Fox and Sudakov's $O(n\log\log n)$ (Random Structures Algorithms 45 (2014), refereed) and the classical $O(n\log n)$ that the 1966 paper asserts; it remains the best refereed bound. The lower bounds are $\liminf f(n)/n\ge\tfrac43$ from Gallai's graph $K_{3,n-3}$ (1966) and $(\tfrac32-o(1))n$ from the complete bipartite graphs $K_{2k+1,n-2k-1}$ , the construction Bucić and Montgomery give for Erdős's 1983 remark, so the constant $C$ is at least $\tfrac32$ and is not determined. The conjecture was known for the random graph $G(n,p)$ and for graphs of linear minimum degree (Conlon, Fox and Sudakov, Theorems 1.3 and 1.4). The search whose scope the Current assessment records predates both claims and found neither a proof nor a disproof.

BM22: Bucić, M. and Montgomery, R., Towards the Erdős-Gallai cycle decomposition conjecture. arXiv:2211.07689 (v1 14 November 2022; v2 14 November 2023, "Final version, accepted for publication"); Adv. Math. 437 (2024), Paper No. 109434, doi:10.1016/j.aim.2023.109434 (Crossref record read; not held); extended abstract in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), 839--852, doi:10.1145/3564246.3585218. Conjecture 1, p. 1; Theorem 2, p. 2; Lemma 26 and the proof of Theorem 2, pp. 23--24; the lower bound, p. 24. Library home: Bucić and Montgomery 2022.
CFS14: Conlon, David and Fox, Jacob and Sudakov, Benny, Cycle packing. Random Structures Algorithms 45 (2014), no. 4, 608--626, doi:10.1002/rsa.20574 (received 2 October 2013, accepted 13 May 2014; cited in the journal's pagination); arXiv:1310.0632 (v2 22 May 2014; not held). Conjecture 1, Theorems 1.2--1.4 and the lower bounds, p. 609. Library home: Conlon, Fox and Sudakov 2014.
EGP66: Erdős, Paul and Goodman, A. W. and Pósa, Lajos, The representation of a graph by set intersections. Canadian J. Math. 18 (1966), 106--112; Section 5, p. 110. Library home: Erdős, Goodman and Pósa 1966 (a scan); the passage is paged at Erdős, Goodman and Pósa 1966, Section 5 (p. 110).
Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97--109; item 11, pp. 101--102. Library home: Erdős 1971; the passage is paged at Erdős 1971, Item 11 (pp. 101-102).
Er76: Erdős, Paul, Problems and results in combinatorial analysis. Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II (1976), 3--17; MR 0465878 (the site's reference text). Library home: Erdős 1976 (the Rényi archive's scan 1976-35.pdf, p. 15; the card carries the row for this problem). Cited by [BM22] (its [15]) among Erdős's collections that mention the conjecture.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42. Library home: Erdős 1981, a retyped copy without the journal's pagination; the passage is on its p. 8 (Part IV, item 3).
Er83b: Erdős, P., On some of my conjectures in number theory and combinatorics. Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983), Congr. Numer. 39 (1983), 3--19; MR 734525 (the site's reference text). Library home: Erdős 1983 (the Rényi archive's scan 1983-15.pdf, item 6, p. 15; the card carries the row for this problem). Cited by [BM22] (its [17]) as the source of the $(\tfrac32-o(1))n$ remark.
Py85: Pyber, L., An Erdős--Gallai conjecture. Combinatorica 5 (1985), 67--79, doi:10.1007/BF02579444 (Crossref record). Not held and not cited by the site; the covering version, quoted on p. 2 of [BM22] and p. 609 of [CFS14].
GGKO21: Girão, A., Granet, B., Kühn, D. and Osthus, D., Path and cycle decompositions of dense graphs. J. London Math. Soc. (2) 104 (2021), 1085--1134, doi:10.1112/jlms.12455; arXiv:1911.05501 (arXiv record read). Not held; quoted on pp. 2 and 24 of [BM22].
AABC25: Akbari, S., Aloni, J., Beikmohammadi, A. and Clow, A., Tight bounds for cycle-edge decompositions and covers. arXiv:2509.01901 (v1 2 September 2025; v2 7 September 2025). Preprint, not held, abstract only; a lead.

Problem 184

Status

Proof claims

Discussion