pipette
ESEspañol

A proof of the Erd\H{o}s--Gallai cycle decomposition conjecture

Jaehoon Kim

PreprintClaims a big step

In the authors' words

In the 1960s, Erd\H{o}s and Gallai conjectured that the edges of every -vertex graph can be decomposed into cycles and edges. We prove this conjecture. Equivalently, every Eulerian graph on vertices can be decomposed into cycles, which confirms Haj\'os' conjecture up to a constant factor.

Main resultLimitation the authors admit

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.