C times n pieces?

The claim, in plain words

Cut the edges of a graph into pieces, each either a cycle (a closed loop through at least three vertices, none repeated) or a single edge. Single edges cannot be avoided: a tree has no cycles, so a tree on n vertices needs n − 1 pieces, and since a cycle uses exactly two edges at each vertex it passes through, a vertex of odd degree always keeps a single edge. By our exact search, the complete graph on 8 vertices (28 edges, 7 at each vertex) needs exactly 7 pieces: three cycles through all 8 vertices and the 4 diameters. On 9 vertices, all 36 edges fall into 4 cycles. The Erdős–Gallai cycle-decomposition conjecture says that a fixed multiple of the number of vertices always suffices, however dense the graph.

As the paper recounts, the conjecture appears in a 1966 paper of Erdős, Goodman and Pósa, which records an O(n log n) bound. Conlon, Fox and Sudakov improved it to O(n log log n) in 2014, and Bucić and Montgomery to O(n log* n), published in 2024. Linear bounds were already known for graphs in which every vertex meets a fixed fraction of all vertices, for random graphs and for graphs of maximum degree at most four. Linear is the best possible order: trees need n − 1, and some complete bipartite graphs need nearly 3n/2. In our exhaustive search of all 1,252 graphs with 1 to 7 vertices, n − 1 pieces suffice up to 6 vertices, and exactly one 7-vertex graph needs 7: a triangle plus four vertices, each joined to all three corners. If pieces may overlap, Pyber showed that n − 1 always suffice; the point here is that every edge is used exactly once.

Result 181 is one OpenAI preprint, A linear cycle-and-edge decomposition of every graph (32 pages, dated September 24, 2026). Its Theorem 1.1: “There is an absolute constant C > 0 such that, for every finite simple undirected graph G with n vertices, E(G) has a partition into at most Cn parts, each of which is the edge set of a cycle or consists of a single edge.” Its Corollary 1.2: a graph with all degrees even splits into at most Cn cycles; and, with an equivalence of Girão, Granet, Kühn and Osthus, large such graphs in which every split into two big parts has proportionally many edges across need at most Δ/2 + δn cycles for any fixed δ > 0, where Δ is the largest degree and every cycle partition needs at least Δ/2.

What it doesn’t claim

A value for C. The constant is shown to exist but never computed. By our arithmetic on the paper’s own parameter choices (Section 7), the cutoff D_* satisfies log₂ D_* ≥ 7.6 × 10¹², and C ≥ 4T(D_*) exceeds D_*, so C is larger than 2 to the power 7.6 trillion, a number with about 2.3 trillion digits; for graphs with fewer than D_* vertices the proof simply takes every edge on its own. Not the best constant: some complete bipartite graphs need nearly 3/2 pieces per vertex, and the paper says nothing about the true value. No efficient algorithm: several steps only show that a suitable random choice exists. Simple graphs only: two vertices joined by k parallel edges need k pieces.

Where it stands

Posted as a preprint

OpenAI, 32 pages, dated September 24, 2026

Peer reviewed

Not yet

Checked in Lean

The main theorem, stated exactly, formalized by OpenAI; not run by us

Last checked October 19, 2026. The preprint has not been revised since it was added to the repository in its initial commit on October 6, 2026. OpenAI published a Lean formalization whose comparator statement is Theorem 1.1 exactly, with the constant chosen before the graph. By our count the proof takes 34 files and 21,451 lines, excluding Mathlib, about 4,000 of them near-copies of other files (source). It includes a proof of Lovász’s path-and-cycle theorem, and proves the routing lemma by a greedy argument instead of the Aharoni–Haxell theorem; like the paper, it does not compute the constant. Corollary 1.2 is not formalized. We found no unproved steps by search; we have not rebuilt the proof. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

1. The accounting problem. A method that pays a cost proportional to the whole graph at every scale picks up a factor from the number of scales.
2. Scales. At scale D (the next is D^0.95), remove a few very long cycles, put the remaining edges into slightly overlapping boxes of at most D^1.02 vertices, and cut each box along sparse cuts until the pieces expand: every cut crosses at least D^0.9 edges per vertex of its smaller side. The cut-off edges are sparse enough for the next scale.
3. Expanding pieces are cheap. Three small random reservoirs; each remaining edge misses at least one. Split those edges into paths with Lovász’s theorem and close each path through its reservoir; a routing lemma built on the Aharoni–Haxell theorem keeps the detours edge-disjoint. An expanding piece with r vertices costs at most 9r parts plus a tiny remainder.
4. Pay once, then fold. One layer of expanding pieces pays for all earlier work and 200 further scales. Low-degree vertices that lie in a chosen expanding piece are glued in pairs, removing at least a third of them; the edges this would spoil, at most two per glued vertex, become single parts.
5. Recurse and lift. The glued graphs are smaller, so induction splits them. A glued cycle may enter a pair at one vertex and leave at the other; a detour through the reserved piece joins them, so each glued cycle lifts to one cycle. A budget Cφ(n)n with φ(n) = max{1/2, 1 − 1/√log n} absorbs the overlap of the boxes.

The paper credits its expansion, matching and path-closing methods to Bucić and Montgomery, and reservoirs and sparse cuts to Conlon, Fox and Sudakov; what it calls new is the induction that saves vertices across scales while reserving edges to lift cycles.

The numbers in the video

• Exact minimum decompositions (our integer program): complete graphs on 3 to 8 vertices need 1, 3, 2, 5, 3 and 7 parts; the complete graph on 9 splits into 4 cycles (a classical construction); complete bipartite graphs with 3 vertices on one side and m on the other need m + ⌈m/3⌉ for m from 2 to 12.
• All 1,252 graphs with 1 to 7 vertices: the largest minimum is n − 1 up to 6 vertices; on 7 vertices it is 7, for one graph only (a 4-cycle, a 6-cycle and 5 single edges).
• The paper’s Figure 1, redrawn: a glued triangle lifts to one cycle (detour lengths schematic).
• The constant: our arithmetic on the paper’s condition (7.21) and parameters (θ = 0.95, K = 200, P₀ = 804).
• The Lean count: our count of the import closure.

Read the source

• A linear cycle-and-edge decomposition of every graph (PDF), 32 pages.
• The Lean scope note.
• The collection’s catalog, where this is result 181.

The paper

OpenAI groups related papers into one result; this one has a single paper.

• A linear cycle-and-edge decomposition of every graph

Transcript

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.