Edge-Disjoint Cycles: OpenAI’s O(n) Proof Untangles a 60-Year Graph Theory Conjecture

How many pieces do you need to take a graph apart? A complete graph can have more than half a billion edges on 32,000 vertices, yet OpenAI’s proof shows that a constant times the vertex count always suffices. The pieces are edge disjoint cycles and single edges. The result settles the Erdős–Gallai cycle decomposition conjecture, posed in 1966. Its decisive move is to pair up vertices in sparse parts, solve smaller graphs, and use edges saved from dense parts to reconstruct the original cycles. The proof works because it saves enough vertices to pay for that reconstruction and keeps track of where every original edge goes.

1. Edge-Disjoint Cycles and the Erdős–Gallai Conjecture

Theorem 1.1 of A Linear Cycle-and-Edge Decomposition of Every Graph says there is an absolute constant C>0C>0 such that every finite simple undirected graph GG on nn vertices admits a partition of its edge set into at most CnCn parts. Each part is the edge set of a simple cycle of length at least three or consists of one edge. “Absolute” means the same constant works regardless of the graph’s density, connectivity, or degree distribution.

The Erdős–Gallai Theorem at a Glance
FeatureWhat the Theorem Says
GraphFinite, simple, and undirected, with nn vertices.
Allowed PiecesSimple cycles of length at least three and individual edges.
Edge AssignmentEvery edge appears once. Different pieces may share vertices.
New BoundAt most CnCn pieces for one universal constant C>0C>0.
SharpnessLinear order is necessary. The optimal constant is open.

Two cycles can pass through the same vertex. Each edge must appear in exactly one piece, so an overlapping cover can fail even if it includes every edge. Removing a duplicate edge from a cycle opens it into a path and can increase the number of pieces needed. A tree has no cycles, so each of its edges must stand alone. A tree on nn vertices already needs n−1n-1 pieces.

2. How Can a Dense Graph Have Only O(n)O(n) Pieces?

	Two edge disjoint cycles, a pentagon and a star, partition all ten edges of the complete graph K₅.
Two edge disjoint cycles, a pentagon and a star, partition all ten edges of the complete graph K₅.

In the complete graph K5K_5, label the vertices from 1 to 5. Every pair is joined, giving ten edges. Walk around the vertices in numerical order to get the first cycle. The unused edges are the five diagonals of that pentagon, and following them gives the second cycle.

Two Cycles Partition the Ten Edges of K5K_5
PieceVertex Order
Outer Pentagon1→2→3→4→5→11\to2\to3\to4\to5\to1
Diagonal Cycle1→3→5→2→4→11\to3\to5\to2\to4\to1

Read each adjacent pair as an undirected edge, including the final step back to 1. Both walks visit all five vertices and together use each of the ten edges once. This is a graph decomposition into two pieces. In bigger graphs a cycle can still use many edges at once. The difficulty is finding cycles that do this efficiently across an arbitrary graph, including regions where some edges belong to no cycle.

3. Sixty Years of Progress Toward the Linear Bound

Erdős, Goodman, and Pósa recorded the O(nlog⁡n)O(n\log n) bound in 1966. Conlon, Fox, and Sudakov improved it to O(nlog⁡log⁡n)O(n\log\log n) in 2014. Bucić and Montgomery obtained O(nlog∗⁡n)O(n\log^* n), published in 2024. Here log∗⁡n\log^* n counts how often you take a base-two logarithm before reaching at most one. It grows slowly, but the bound still leaves a multiplier that depends on nn.

Earlier results already gave linear bounds for some classes, including graphs of linear minimum degree. General graphs can mix regions of very different densities. Breaking them down by scale makes their edges easier to handle, but a method that spends a linear number of pieces at each scale can accumulate too much cost. The new proof charges the work across a whole prefix of scales to the vertices saved at one selected layer.

4. OpenAI’s Proof Roadmap in Five Stages

1. Split by scale. Take out long cycles and separate the remaining edges into small boxes. Inside each box, extract well-connected pieces and pass the sparse remainder to a lower scale.

2. Save edges for connections. Select one expanding layer that can pay for the prefix. Reserve some of its edges to repair cycles later. Keep enough expansion to process each piece into completed parts and a much smaller residue.

3. Route without conflicts. Use expansion to find short paths that avoid forbidden vertices. Choose the paths together so that two connections never spend the same edge and connections within one new cycle can fit together.

4. Fold and lift. Pair eligible vertices in the sparse remainder to make smaller graphs. Decompose those graphs by induction, then use reserved paths to turn the quotient cycles back into simple cycles of the original graph.

5. Balance the count. Use the saved vertices to pay for the work already done. A stronger inductive estimate covers the extra vertex counts introduced by overlapping boxes.

5. Splitting Graphs into Small Boxes and Expanding Pieces

Section 5 starts with a graph of order NN, meaning its number of vertices, and average degree at most DD. Cycles of length at least D1.01D^{1.01} each remove enough edges that at most N/(2D0.01)N/(2D^{0.01}) can be taken. Once they are gone, any subgraph larger than D1.02D^{1.02} has a set with a small external neighborhood. Stronger neighborhood expansion would force a long cycle.

The split copies just that neighborhood into both children. Every edge is assigned to one child, so the overlap is in vertex counts only. A potential for the binary splitting process bounds the total box order by (1+2/log⁡D)N(1+2/\log D)N. Within a box, repeatedly cut wherever there are too few edges crossing relative to the smaller side. In a surviving piece RR of order rr, let ∂RU\partial_R U be the set of edges crossing from UU to its complement. The cut expansion bound h=D0.90h=D^{0.90} means that every UU satisfies

|∂𝑹𝑼|≥𝒉min⁡{|𝑼|,𝒓−|𝑼|}.\boldsymbol{|\partial_R U| \ge h\min\{|U|,r-|U|\}.}

Charge each removed cut to its smaller side. A vertex can receive that charge only when its current piece shrinks by at least half. The residual box graph consequently has average degree at most D0.95D^{0.95} for sufficiently large DD. It keeps the full box vertex set, and its edges enter the next scale.

6. Three Reservoirs Turn Paths Into Simple Cycles

A path closes through a disjoint reservoir, illustrating one way the proof builds edge disjoint cycles.
A path closes through a disjoint reservoir, illustrating one way the proof builds edge disjoint cycles.

Partition the edges of a spanning expander into three expanding subgraphs. Sample three mutually disjoint small vertex sets, one in each subgraph, so that each set still supports expansion and all outside vertices have many neighbors in their respective reservoir. For each reservoir, reserve its internal expander edges and two edges from every outside vertex to distinct representatives. The choices cap the load at each representative.

Three sets suffice because an edge has only two endpoints. Every unreserved edge therefore avoids at least one reservoir and can be assigned to a complementary graph. A consequence of Lovász’s theorem partitions each complementary graph into paths with at most two endpoint occurrences per vertex. The two reserved edges at an outside vertex cover both possible occurrences.

A path closes by entering the reservoir at one representative and leaving at the other. If they coincide, the two entering and leaving edges suffice. Every added internal vertex lies outside the original path, making the cycle simple. For a piece of order rr, Section 4 completes at most 9r9r parts, including unused access edges taken singly. The remaining edges lie inside the reservoirs, whose combined order is at most any prescribed positive fraction of rr once the scale cutoff is high enough.

7. Hypergraph Matching Routes Paths Without Reusing Edges

A good path for one demand can block a later demand. The expansion threshold in Lemma 3.1 makes room for all of them. With maximum route length ℓ\ell, endpoint load kk, team size bb, and forbidden-set size zz, the lemma requires

𝒉≥64(ℓ2(𝒌+𝒃)+𝒛).\boldsymbol{h\ge64\bigl(\ell^2(k+b)+z\bigr).}

Here ℓ\ell is set by the order and expansion of the router. The proof treats each candidate path as a set of resources in a hypergraph. It claims the graph edges it uses and a token for each internal vertex paired with its team label. Disjoint choices prevent edge reuse globally. The tokens prevent two paths in the same team from using the same internal vertex, while each demand separately forbids specified vertices from its interior.

Aharoni–Haxell’s matching theorem gives one compatible choice per demand if every subfamily of mm demands has a union of candidates containing a matching larger than s(m−1)s(m-1), where ss bounds candidate resource-set size. To establish this, the paper assumes a small maximum matching blocks a subfamily. Bounded endpoint load supplies many distinct roots, and bounded team size keeps token exclusions manageable. After deleting blocked edges and demand-specific forbidden vertices, expansion grows unions of balls around those roots. Repeatedly halving the root set and regrowing the union isolates a root whose ball reaches more than half the vertices. If both endpoint balls exceeded half the router, their intersection would give a short path using only available resources. Maximality rules that out. This contradiction supplies simultaneous routes for reservoir closures and cycle lifting.

8. Pair Folding Shrinks the Graph

After a fixed gap in scales, group the tiny descendant boxes into batches of order at most D0.30D^{0.30}. Within a batch, pair low-degree vertices in sufficiently large intersections with a selected expanding piece. The degree cap a=D0.01a=D^{0.01} applies to the union of all batches in the parent box. A set must have at least D0.03D^{0.03} eligible vertices, enough to make accidental collisions rare under random pairing.

Low degree on the paired side alone is insufficient. A vertex adjacent to many members of a folding set can lose an edge each time two of its neighbors become one vertex. The proof removes edges to these heavy neighbors first. It partitions those edges into paths, takes terminal edges at heavy endpoints singly, and closes the surviving paths using reserved routes.

Each pair then becomes one quotient vertex. Edges within a pair become loops, and distinct edges between the same quotient vertices may collide. An expectation bound shows there is a pairing for which taking the loops and surplus parallel edges singly costs at most twice the total folding-set order. Each retained quotient edge keeps one original representative.

9. Cycle Lifting Reconstructs Simple Cycles

	A reserved switch path lifts a quotient triangle to a five-edge cycle in the proof about edge disjoint cycles.
A reserved switch path lifts a quotient triangle to a five-edge cycle in the proof about edge disjoint cycles.

Suppose a quotient cycle arrives at a folded vertex through the representative edge ending at uu and leaves through the edge starting at its twin vv. A switch path in the reserved router joins uu to vv. If the two endpoints coincide, the representatives already join. Each original endpoint used by this quotient cycle is forbidden inside any of its switch paths.

For switches in the same router, the cycle defines a team, so their interiors are disjoint. For example, if a quotient triangle has one switch and its route is u→x→vu\to x\to v, its three representative edges plus the two route edges form a five-edge cycle. The intermediate vertex xx must avoid every representative endpoint. Switches in different routers of the same parent box lie in vertex-disjoint pieces. Since the quotient cycle visits distinct fibers, the original endpoints at different visits are distinct too. Together these facts make the lift a single simple cycle. A quotient singleton edge simply lifts to its original representative.

The proof bounds each vertex’s routing load across all batches by charging every demand-end occurrence to a different incident edge of the batch union. All routes use reserved edges, each at most once. A separate spanning expander remains untouched, allowing Section 4 to process what is left of each selected piece.

10. The Final Induction Gives the Linear Bound

At layer jj, the scale is Dj=n(0.95)jD_j=n^{(0.95)^j}. Write SjS_j for the total order of that layer’s expanding pieces, counting pieces in different boxes separately. Section 7 finds an index ii where the total piece order through layer i+200i+200 is at most a fixed multiple of SiS_i. If the bound fails at a candidate index, a larger layer lies within the next 200 steps. Moving to it preserves the bound on the prefix already passed and eventually stops.

Set D=DiD=D_i and S=SiS=S_i. In the nonterminal case, completed work costs O(S+n/log⁡D)O(S+n/\log D) pieces. Quotient orders sum to at most

𝒏−𝑺3+𝑶(𝒏log⁡𝑫).\boldsymbol{n-\frac{S}{3}+O\!\left(\frac{n}{\log D}\right).}

The remaining expander residues have total order at most S/100S/100. Taking the constant CC sufficiently large lets the net vertex savings pay for the work proportional to SS. Boxes can overlap, so a residual O(n/log⁡D)O(n/\log D) excess in the order count still needs to be paid for.

The induction uses the stronger budget Cϕ(n)nC\phi(n)n, with ϕ(1)=1/2\phi(1)=1/2 and, for n>1n>1,

𝝓(𝒏)=max⁡{12,1−1log⁡𝒏}.\boldsymbol{\phi(n)=\max\!\left\{\frac12,1-\frac{1}{\sqrt{\log n}}\right\}.}

Each quotient has order at most D0.30D^{0.30}. The difference ϕ(n)−ϕ(D0.30)\phi(n)-\phi(D^{0.30}) is bounded below by a positive constant times 1/log⁡D1/\sqrt{\log D}. This dominates the overlap charge of order 1/log⁡D1/\log D at large scales. At the cutoff, bounded average degree makes it affordable to take the final sparse edges singly, while any small expander residues still go to induction. Since ϕ(n)≤1\phi(n)\le 1, the stronger bound implies CnCn.

11. Eulerian Graphs and Optimal Bounds

An Eulerian graph, in the paper’s convention, has even degree at every vertex and may be disconnected. Removing the cycle parts preserves even degrees. The singleton edges therefore form an even graph, which can be split into cycles using at most as many parts as there were singleton edges. This yields an Eulerian graph cycle decomposition within the same linear bound.

A vertex of maximum degree Δ(G)\Delta(G) needs at least Δ(G)/2\Delta(G)/2 cycles to cover its incident edges, because each simple cycle contributes at most two there. Corollary 1.2 reaches this lower bound up to an arbitrarily small linear error when every cut with both sides of size at least εn\varepsilon n has at least p|A||B|p|A||B| crossing edges, with AA and BB the sides and p>0p>0 fixed. The required ε>0\varepsilon>0 and minimum graph size depend on pp and the permitted linear error. For general cycle-and-edge partitions, certain complete bipartite graphs require (3/2−o(1))n(3/2-o(1))n pieces, where o(1)o(1) tends to zero as nn grows. An odd-sized smaller side forces at least one singleton at every vertex on the larger side, and the cycles have limited length. The optimal universal constant remains open.

12. Lean Verification, Scope, and Remaining Questions

OpenAI’s release attributes its results to an internal frontier model. The five stages above reconstruct the dependencies in the written proof, without assigning a chronology to the model’s discoveries. The Family 181 Lean scope note specifies the universal linear bound for finite simple graphs, including edgeless graphs. The Lean file proves the main theorem, and an independent Comparator replay reports acceptance by Lean’s kernel and the separate nanoda kernel. The replay checks the formal statement within Lean’s definitions. Corollary 1.2 and the prose arguments used to explain it belong to the manuscript’s exposition.

The proof gives an existence bound on the number of pieces. It leaves open the sharp universal constant and supplies no practical runtime benchmark for finding such a partition. Its reusable insight is that edge-disjoint cycles can survive a reduction in vertex count when the original edges and the routes that reconnect them are accounted for together. Follow Binary Verse AI for more research explainers on graph theory and machine-checked mathematics.

What is the Erdős–Gallai cycle decomposition conjecture?

It states that every finite simple undirected graph with n vertices has an edge partition into at most Cn simple cycles and single edges for one universal constant C. OpenAI’s proof establishes this linear bound.

Why are single edges necessary in a cycle decomposition?

A tree has no cycles and a tree on n vertices has n − 1 edges. For such a graph every edge must be taken as a separate piece.

Can edge-disjoint cycles share vertices?

Yes. Two cycles may pass through the same vertex, but they cannot share an edge. Each edge belongs to exactly one part of the decomposition.

How does OpenAI’s proof improve the previous result?

The previous general bound was O(n log* n). OpenAI’s proof achieves O(n) by splitting the graph at several scales, folding pairs of vertices, using reserved paths to restore cycles, and balancing these costs through a strengthened induction.

Does the proof determine the minimum number of cycles needed?

The theorem proves a universal linear upper bound for the total number of cycles and single edges. The optimal constant remains open. Certain complete bipartite graphs require at least (3/2 − o(1))n pieces, with o(1) tending to zero as n grows.

Does the result apply to Eulerian graphs?

Yes. Every finite simple graph with all degrees even has an edge partition into O(n) cycles. After removing the cycle parts from the original decomposition, the singleton edges still give an even graph, which can itself be partitioned into cycles.

Has OpenAI’s Erdős–Gallai proof been formally verified in Lean?

Yes. Family 181 formalizes the main theorem, and independent checks have reported successful kernel replay. The replay checks the formal theorem, while the manuscript presents the detailed mathematical exposition.

Leave a Comment