PreprintCC BY-NC-SA 4.0arXiv
A proof of the Erdős-Gallai cycle decomposition conjecture
Abstract
In the 1960s, Erdős and Gallai conjectured that the edges of every n-vertex graph can be decomposed into O(n) cycles and edges. We prove this conjecture. Equivalently, every Eulerian graph on n vertices can be decomposed into O(n) cycles, which confirms Hajós' conjecture up to a constant factor.
Related
- The Erdős-Gallai bound for consecutive even cycle lengths
- Proof of the Erdős-Szemerédi sunflower conjecture
- A proof of the strong Erdős--Frankl--Füredi cover-free conjecture
- The Erdős--Sós Conjecture: A visual exposition of the proof discovered by GPT-6 Astra
- Counting Admissible Sets of Integers: A Proof of the Erdős--Nicolas--Sárközy Conjecture
BibTeX
@misc{kim2026proof,
title = {{A proof of the Erdős-Gallai cycle decomposition conjecture}},
author = {Jaehoon Kim},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07840},
eprint = {2610.07840},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07840},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - A proof of the Erdős-Gallai cycle decomposition conjecture
AU - Jaehoon Kim
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.07840
UR - https://arxiv.org/abs/2610.07840
AB - In the 1960s, Erdős and Gallai conjectured that the edges of every n-vertex graph can be decomposed into O(n) cycles and edges. We prove this conjecture. Equivalently, every Eulerian graph on n vertices can be decomposed into O(n) cycles, which confirms Hajós' conjecture up to a constant factor.
ER -