{"id":"openai-math/A-linear-cycle-and-edge-decomposition-of-every-graph","pdf":"https://github.com/openai/math/blob/main/preprints/A-linear-cycle-and-edge-decomposition-of-every-graph-September-24-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-linear-cycle-and-edge-decomposition-of-every-graph-September-24-2026","tags":["graph-theory","cycle-decomposition","combinatorics"],"score":0,"title":"A linear cycle-and-edge decomposition of every graph","domain":"Combinatorics","family":"181","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.CO","summary":"We prove that every finite simple undirected graph on n vertices has an edge partition into at most $`Cn`$ simple cycles and single edges, for an absolute constant C . This resolves the Erdős–Gallai cycle decomposition conjecture positively.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":true,"family_title":"The Erdős–Gallai cycle-decomposition conjecture"}