The Erdős–Gallai cycle decomposition theorem

OpenAI's proof (2026) of the Erdős–Gallai cycle decomposition conjecture: the edges of every graph with n vertices can be partitioned into at most Cn cycles and single edges. Lovász's path-and-cycle theorem, Haxell's hypergraph condition, routing in graphs with cut expansion, splitting at a scale, random vertex samples, closing paths through reservoirs, pair folding with lifting of cycles, and an induction over scales with a sublinear potential.

Eight lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

1. Paths, cycles and Lovász's decomposition theorem
2. Disjoint representatives in hypergraphs
3. Routing in graphs with cut expansion
4. Splitting a graph at a scale
5. Random sampling in expanding graphs
6. Closing paths through reservoirs
7. Folding pairs and lifting cycles
8. The linear bound

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites

• Basic graph terminology: degrees, paths, cycles, components.