---

Statement

"Theorem 1.4. Every graph $G$ on $n$ vertices with minimum degree $cn$ can be decomposed into at most $O(c^{-12}n)$ cycles and edges."

For fixed $c>0$ this is a linear bound $O_c(n)$; the site writes it as "$O_\epsilon(n)$ cycles and edges suffice if $G$ has minimum degree at least $\epsilon n$".

Source. D. Conlon, J. Fox and B. Sudakov, Cycle packing, Random Structures Algorithms 45 (2014), no. 4, 608--626, doi:10.1002/rsa.20574; printed p. 609 = PDF p. 2 of the publisher's version, read on the page image. The artifact is identified in the source digest.

Read depth. Claims checked: the statement was read clause by clause on the page image of p. 609. The proof (Sections 5--6) was not read.

Proof pointer

Sections 5--6 (pp. 617--625): Section 5 proves the conjecture for $d$-cut dense graphs (Theorem 5.3, which uses Corollary 4.3 from the random-graph section), and Section 6 deduces Theorem 1.4 on pp. 624--625; not reconstructed here. The asymptotically sharp constant for this class, $(\tfrac32+o(1))n$ for large graphs of linear minimum degree, is due to Girão, Granet, Kühn and Osthus, as recorded on p. 2 of Bucić and Montgomery (not held here).

Dependencies

Internal lemmas of the paper and of the proof of Theorem 1.3.

Bears on

• Problem 184: the conjecture holds for graphs of linear minimum degree, the special case the site's commentary names; not the general statement.