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