In September 2026, OpenAI released a preprint (OpenAI 2026) announcing a proof of the Erdős–Gallai cycle decomposition conjecture, a long-standing problem in graph theory. The result states that the edges of any graph with vertices can be partitioned into at most cycles and single edges, where is an absolute constant.
The problem is very easy to formulate, but proving it turned out to be surprisingly difficult.
Let us recall some definitions. A graph consists of a set of vertices, some pairs of which are joined by edges. A cycle is a sequence of distinct vertices such that consecutive vertices are joined by edges, and is also joined to .
We say that a graph is decomposed into cycles and single edges if every edge of the graph belongs to exactly one of these pieces. The cycles may share vertices, but they must not share edges.
For example, consider the complete graph , in which every pair of four vertices is joined by an edge. Its six edges can be partitioned into a cycle of length four and two single edges, corresponding to the two diagonals of the cycle.
The interesting question is how many pieces are necessary for an arbitrary graph.
Of course, a graph with vertices has at most edges, so we can always decompose it into at most single edges. But can we do substantially better by combining many edges into cycles?
The Erdős–Gallai conjecture predicts that a linear number of pieces always suffices.
There is an obvious reason why we must allow single edges in addition to cycles. A tree is a connected graph containing no cycles. Every tree with vertices has exactly edges, and none of them can be included in a cycle. Thus, a tree requires single-edge pieces.
Consequently, no universal bound smaller than linear in is possible.
The remarkable prediction was that this simple obstruction essentially determines the correct order of growth for every graph, no matter how complicated its structure.
The problem was discussed in a 1966 paper of Erdős, Goodman, and Pósa (Erdős et al. 1966), who established an upper bound of order Here means that is at most a constant multiple of for all sufficiently large , and denotes the logarithm.
The logarithmic factor proved very difficult to remove.
In 2014, Conlon, Fox, and Sudakov (Conlon et al. 2014) obtained the improved bound
Then, in 2024, Bucić and Montgomery (Bucić and Montgomery 2024) made another breakthrough, proving that every graph admits a decomposition into cycles and single edges. Here denotes the number of times we must repeatedly apply the logarithm to before the result becomes at most .
The function grows extraordinarily slowly. Nevertheless, it is unbounded, so this result did not settle the conjecture.
The new OpenAI preprint (OpenAI 2026) claims to remove this final factor.
Here a graph is called simple if it has no loops or multiple edges.
Notice that the constant does not depend on the graph, its number of edges, or its vertex degrees. The result applies equally to sparse graphs, dense graphs, and graphs with highly irregular structure.
The theorem is optimal in its order of growth. As we observed, trees already require pieces. In fact, more sophisticated examples show that the smallest possible universal constant must be at least asymptotically. The optimal value of remains unknown.
There is also an interesting consequence concerning graphs in which every vertex has even degree. Such graphs are called Eulerian.
It is a classical fact that the edges of every Eulerian graph can be decomposed into cycles. Indeed, if a graph has even degrees and contains an edge, then it contains a cycle. Removing that cycle leaves another graph with even degrees, so the process can be repeated.
The new theorem shows that an Eulerian graph with vertices can always be decomposed into at most cycles, with the same absolute constant .
To see this, first apply the theorem and remove all the cycle pieces. The remaining edges form a graph in which every vertex still has even degree, since each removed cycle decreases the degree of every vertex it meets by exactly two. We can therefore partition the remaining edges into cycles. Since each such cycle replaces at least one of the original single-edge pieces, the total number of pieces does not increase.
Thus, the theorem also settles the corresponding linear cycle decomposition problem for Eulerian graphs.
In an earlier blog post, we discussed the decomposition of complete graphs into cycles of prescribed lengths. There, the central challenge was determining exactly when the necessary divisibility conditions guarantee a decomposition.
The present theorem addresses a different problem. We allow cycles of arbitrary lengths, together with single edges, and ask for an upper bound on the number of pieces. This flexibility makes a decomposition possible for every graph, but obtaining a bound proportional to the number of vertices remains highly nontrivial.
Let us briefly discuss the proof.
The authors build on the methods developed by Conlon, Fox, and Sudakov, and especially by Bucić and Montgomery. A central idea is to divide a graph into smaller pieces while identifying highly connected regions, known as expanders. These regions have many edges connecting different groups of vertices and therefore contain numerous paths that can be used to join other parts of the graph.
The authors repeatedly simplify the graph by working at different scales. They reserve some edges inside the expanding regions to connect paths, while reducing the remaining problem to smaller graphs.
The main difficulty is to prevent the number of cycles and single edges produced at successive stages from becoming too large. Earlier methods accumulated an extra factor of through this repeated process.
The new proof introduces a more efficient inductive argument. By carefully combining vertices when passing to smaller graphs, the authors save enough vertices to compensate for the additional pieces introduced at each stage. The reserved paths in the expanding regions then allow cycles in the smaller graphs to be reconstructed as cycles in the original graph.
This makes it possible to obtain a bound of the form , with no additional logarithmic factors.
The OpenAI repository also reports a formalization of the main theorem in Lean, although independent scrutiny of the mathematical argument remains important.
If confirmed, this result will settle a conjecture dating back approximately sixty years. Its conclusion is strikingly simple: no matter how many edges a graph has or how irregularly they are arranged, all its edges can be organized into only linearly many cycles and single edges.