Family 181CombinatoricsLeanNot yet digested
The Erdős–Gallai cycle-decomposition conjecture
Proves that the edges of every finite simple undirected graph on n vertices can be partitioned into at most simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai cycle-decomposition conjecture, bounding the number of pieces linearly even for dense graphs.
Manuscripts in this family · 1
A linear cycle-and-edge decomposition of every graph
Sep 24, 2026·main.pdfLean
We prove that every finite simple undirected graph on n vertices has an edge partition into at most simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai cycle decomposition conjecture positively.