The Erdős–Gallai cycle-decomposition conjecture

The explanation

Draw four points and join every pair: six links in all. Try to split the links into pieces of two kinds. A piece can be a cycle, a closed loop that visits each of its points once. Or a piece can be a single link. Every link must land in exactly one piece. One way uses a loop around all four points, plus the two diagonal links left over. That is three pieces. A check of every option shows that three is the fewest possible.

Why can't it be done with fewer? Each point has three links, an odd number. A cycle uses two links at each point it passes through. So at every point at least one link must be a single piece. Each single link serves two points, so at least two are needed.

Single links can't be avoided in general. A tree is a network with no loops at all, so it has no cyclesSource 1. A tree on n points has n − 1 links, and every one must be its own pieceSource 2. Paul Erdős and Tibor Gallai conjectured that this is about the worst case. Their conjecture says some fixed number C works for every network: at most C times n pieces always sufficeSource 3.

Progress came in slow steps. The question appears in a 1966 paper of Erdős, Goodman and Pósa, which gave a bound of order n times log nSource 4. A logarithm grows slowly, but it still grows without limit. In 2014, Conlon, Fox and Sudakov improved this to n times log log nSource 5. Then Bucić and Montgomery reached n times log* n, published in 2024Source 6. Here log* n counts how many times you take a base-2 logarithm before reaching 1. For 10⁸⁰, about the number of atoms in the universe, that count is only 5. Still, it is not a fixed number.

The rule that pieces share no links is the heart of the problem. If pieces may overlap, Pyber showed in 1985 that n − 1 pieces always cover a networkSource 7. But an overlapping cover does not give a splitSource 8. Removing the repeated links can break its loops into many open paths.

This paper proves the conjectureSource 9. Every finite network on n points splits into at most Cn cycles and single links, for one fixed C. The order n cannot be improved, because of treesSource 2. Some complete two-sided networks even need about 1.5n piecesSource 10. The paper does not say how small C can be.

The obstacle was cost that grows with scale. The proof works on the network at many sizes, from coarse to fine. Paying a cost that matches the whole network at every size piles up an extra factorSource 11. The paper instead charges the work to one well-connected layer. Then it merges pairs of points in that layer, which saves a fixed share of its pointsSource 12. The smaller merged network is split by the same argument, one size down. Spare paths inside the layer then rejoin each merged pair. So each loop in the merged network becomes one true loopSource 13.

There is a clean consequence. Call a network even if every point has an even number of links. Then single links are no longer needed. Every even network on n points splits into at most Cn cycles aloneSource 14. For example, join every pair among five points. Each point then has four links. The ten links split into two loops of five: a pentagon and a five-pointed star.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It states that one fixed constant C works for every finite network, including empty and small ones. It does not pin down the best value of C. No specialist review of the paper has been published.

What it doesn't show. This does not give the best value of the constant.