---

Claim. The edges of every graph on $n$ vertices can be decomposed into $O(n)$ cycles and single edges, the statement of Problem 184; in its notation, $f(n)=O(n)$. This is Theorem 1.1 (p. 1) of Jaehoon Kim, A proof of the Erdős–Gallai cycle decomposition conjecture, arXiv:2610.07840, submitted on 6 October 2026 (v1, the claim's date) and revised on 9 October 2026 (v2, the version cited here), carded at its card with Theorem 1.1 paged. Graphs are finite and simple, and a decomposition is a partition of the edge set into the edge sets of cycles and single edges (Section 1.2), which is the problem's reading. The proof (Section 2.1, pp. 3--4) runs one procedure on the current graph, with an integer $k$ fixed by the two main theorems. (a) If a vertex has degree between $1$ and $k-1$, its edges are recorded as single edges. (b) Otherwise, if there is a heavy cycle, one with at least $b^{3/2}$ vertices of degree at most $b$ for some real $b\ge1$ (Definition 1.2, p. 2), it is recorded. (c) Otherwise the graph is light, and Theorem 1.3 (p. 2) gives a nonempty set $S$ that induces minimum degree at least $|S|^{1/1000}$ and has at least $|S|/12$ vertices with at most two neighbors outside $S$; Theorem 1.4 (p. 2) decomposes the edges inside $S$ into at most $k|S|$ cycles and edges. Step (a) runs at most $n$ times. The potential $\sum_v\bigl(1-1/\sqrt{d(v)+1}\bigr)$ starts below $n$ and drops by at least one at each step (b). Each vertex is among the $|S|/12$ vertices of at most one step (c), since it is isolated afterwards. So at most $14kn$ cycles and edges are recorded. Theorem 1.3 is the paper's new ingredient, and its proof (Sections 3--5) uses no expanders. Theorem 1.4 (Section 6) extends Conlon, Fox and Sudakov's theorem for linear minimum degree to graphs with minimum degree at least $n^{\varepsilon}$, which decompose into at most $C_\varepsilon n$ cycles and edges, using Bucić and Montgomery's robust sublinear expanders. The paper also notes (p. 2) that every Eulerian graph on $n$ vertices therefore decomposes into $O(n)$ cycles, Hajós's conjecture up to a constant factor. The constant is large and not optimized (Section 7).

Depends on. Nothing in this wiki. The paper proves its lemmas itself, apart from the results it quotes as Theorems 6.2 and 6.3 (p. 15). From Bucić and Montgomery (numbered as in arXiv:2211.07689v2) it takes three results: every graph on $m$ vertices decomposes into at most $m$ paths (their Corollary 22); removing at most $4sm\log m$ edges leaves a union of $s$-expanders whose orders sum to at most $2m$ (their Lemma 14); and every graph on $m\ge2$ vertices decomposes into at most $6m$ cycles and $O(m\log^{274}m)$ edges (their Theorem 24). From Conlon, Fox and Sudakov it takes a linear decomposition of $(\rho,c)$-sparse graphs (their Corollary 4.3) and the sparseness of $G(m,p)$ for $p\le m^{-\rho}$ (their Lemma 4.4). It also uses Chernoff's bound. Lemma 6.4 is a variant of Bucić and Montgomery's Lemma 15 with its own short proof.

Versions and AI use. Version 1 (32 pages) states Theorem 1.1 with an absolute constant $C$ and the Eulerian form as Corollary 1.2. Its main ingredients are Theorems 1.4 and 1.5, and its count is $52kn$. Version 2 (22 pages) renumbers them as Theorems 1.3 and 1.4 and lowers the count to $14kn$. Its "Note added" (p. 21) says that it simplifies the first version. Heavy cycles are defined by degrees instead of vertex weights, which removes logarithmic factors from Sections 3--5. In Section 6 a deterministic routing lemma (Lemma 6.6) replaces a random coloring with $\Theta(\log^3n)$ colors, and the edges of the expanders are no longer treated separately. The same note says that OpenAI announced an independent proof after version 1 was submitted and before it appeared. It cites the release's manuscript as released on 6 October 2026, and it contrasts the release's induction on the number of vertices through quotient graphs with the paper's two separate theorems joined by a short procedure. Both versions have a section "Use of AI tools" just before the references (p. 26 of version 1, p. 21 of version 2); version 1 places its appendix after the references. The section states that the author made extensive use of ChatGPT (OpenAI) and Claude (Anthropic) in developing the arguments and in preparing the text and figures. It also states that the author has verified all results and takes full responsibility for the content. Kim, of KAIST, is the paper's only author.

Standing. Claimed. The preprint is on arXiv (v1 6 October 2026, v2 9 October 2026), is not refereed and has no Lean formalization, and no outside review is known. Here the statement of Theorem 1.1 and its deduction from Theorems 1.3 and 1.4 (Section 2.1) were checked. The proofs of Theorems 1.3 and 1.4 (Sections 3--6) were read only through the paper's own outline (Sections 2.2--2.3) and were not checked. The preprint was never on the erdosproblems.com proof-claim tab, which closed to new claims on 6 October 2026. On 8 October 2026 the user efiebig pointed to it in a post in the comment thread of the curator's blog post "Erdős problems in the OpenAI proofs" (post). That post is not the author's, so no submission is recorded. The problem's standing rests on OpenAI's accepted claim; if accepted, this claim would be a third proof, independent of it and of Coffey's pending claim.