A 1960s GRAPH PUZZLE FINALLY CLOSES

Take some points and join some pairs of them with lines: mathematicians call this a graph, the points its vertices and the lines its edges. A cycle is a closed loop that visits distinct vertices and returns to its start. A natural question is whether the edges of a graph can be split up — each edge used exactly once — into cycles.

The answer has long been known, as the paper recalls: it is possible exactly when every vertex touches an even number of edges. Such graphs are called Eulerian. The next question is how many cycles are needed. And for graphs where cycles alone will not do, one also allows single edges as pieces.

The conjecture

In the 1960s, Erdős and Gallai conjectured that the edges of every graph with n vertices can be split into a number of cycles and single edges at most proportional to n — written O(n). Erdős included it in several of his collections of open problems. A related conjecture by Hajós asks for at most (n − 1)/2 cycles in every Eulerian graph.

Linear is the best one could hope for: Erdős showed that some graphs need about 1.5 n pieces. The question was whether some constant times n always suffices.

Fifty years of creeping bounds

Erdős and Gallai themselves noticed a simple method: repeatedly remove the longest cycle. It gives about n log n pieces — and, according to the paper, that remained the best general bound for almost fifty years. More recently, Conlon, Fox and Sudakov lowered it to n log log n, then Bucić and Montgomery to n log* n, where log* n — the number of times one must take a logarithm to get below one — grows unimaginably slowly. These approaches worked in rounds, and each round cost about n cycles, so the number of rounds always crept into the final count. The conjecture had also been proved for special families, such as random graphs.

Weights that pay for loops

Jaehoon Kim, of KAIST in South Korea, now proves the conjecture: there is a fixed constant C such that every graph with n vertices splits into at most Cn cycles and edges. As a corollary, Hajós’ conjecture holds up to a constant factor.

The proof abandons rounds. A single procedure removes cycles and edges one at a time, and the total is controlled by two quantities that each stay below a constant times n.

• A potential based on degrees. Each vertex gets a weight that shrinks with its number of edges, roughly 1 / (degree × log² degree). A cycle is heavy if the weights of its vertices add up to at least 1. Removing a heavy cycle lowers an overall “potential” by at least 1, and that potential starts at no more than a constant times n. So heavy cycles can only be removed O(n) times.
• The number of vertices. When no heavy cycle is left, the graph is “light” — and the main new theorem shows that a light graph with large degrees must contain a dense, almost closed-off region. That region is split into a number of cycles and edges proportional to its size, after which at least a fiftieth of its vertices are left with at most two edges and drop out for good. Since each vertex can drop out only once, this part also costs O(n).

Inside dense parts of the graph, pieces of paths are closed into a single cycle by joining paths routed through “expanders”; a random colouring keeps the joining paths of one cycle apart. — Figure 3, Kim (2026), arXiv:2610.07840.

To split those dense regions, the proof extends Bucić and Montgomery’s toolkit of robust “expanders” — graphs in which every set of vertices has many neighbours — and colours vertices at random so that the connecting paths of the same cycle never collide.

What is still open

The constant C is enormous, and the author did not try to optimise it. Finding the best constant — at least 1.5 — remains open, as do the exact Hajós conjecture and a related conjecture by Gallai on splitting graphs into paths. The weighting trick only needs weights whose sum converges, and the author suggests it could serve in other decomposition problems.

This is a single-author preprint, not yet checked by peer review.

Conflict of interest. The author states that they made extensive use of ChatGPT (OpenAI) and Claude (Anthropic) in developing the arguments and preparing the text and figures, and that they verified all results and take full responsibility for the paper. The text you are reading was written by Claude as well.