Erdős Problem #184
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, cycles.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A graph's edges can be partitioned into edge-disjoint simple cycles and single edges: every original edge must appear in exactly one piece. Erdős and Gallai conjectured that there is an absolute constant \(C\) such that every graph with \(n\) vertices has such a decomposition using at most \(Cn\) pieces.
The word decomposition means every edge is covered, not merely that some cycles and edges can be chosen. Cycles may share vertices but not edges, and an isolated unused vertex needs no piece.
A small example
A triangle \(K_3\) has three edges and can be covered by one three-edge cycle, rather than three separate edge pieces. A tree contains no cycles, so each edge must remain a singleton; a tree on \(n\) vertices has \(n-1\) pieces. These show how cycles can save pieces and why linear order is the natural target.
A graph with no cycles has no choice about the decomposition. A graph with cycles can always remove a simple cycle and repeat until no cycle remains, but a naive removal argument alone does not guarantee at most \(Cn\) pieces.
What is known
The conjectured universal linear upper bound remains OPEN. Erdős, Goodman and Pósa (1966) proved that \(O(n\log n)\) edge-disjoint cycles and edges suffice. Bucić and Montgomery, Towards the Erdős–Gallai cycle decomposition conjecture, improved the upper bound to
pieces, where \(\log^*\) is the iterated logarithm function. Although \(\log^*n\) grows extraordinarily slowly, it is unbounded, so this is not a proof of \(O(n)\).
Conlon, Fox and Sudakov proved a positive linear bound \(O_\varepsilon(n)\) when the graph has minimum degree at least \(\varepsilon n\). That restricted minimum-degree result does not cover arbitrary sparse graphs.
The maintained Erdős #184, updated April 2026, records that \(K_{3,n-3}\) requires at least \((1+c)n\) pieces for some absolute \(c>0\), showing that the optimal universal constant cannot simply be one. Dropping edge-disjointness produces a different and potentially weaker covering question.
GCL's current state
Pinned and maintained status: OPEN. Original issue: #1453. The \(O(n\log^*n)\) result is attributed to Bucić–Montgomery (2022) from the source catalogue, and no full original proof was independently recreated. A formal statement in newer upstream sources is not by itself a protected proof certificate.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded successor enumerates small graphs and computes the minimum partition into simple cycles and remaining singleton edges using exact edge-bitmask dynamic programming. Acceptance: a triangle needs one piece, a tree needs exactly its edge count, and no edge is duplicated or omitted. Report numerical values for small complete bipartite graphs, while separating finite checks from the conjectured universal linear bound.
Sources and claim boundaries
- Erdős #184, original [EGP66] and improvements [BM22], [CFS14].
- Original GCL issue #1453.
No linear decomposition theorem, independent complete source-proof certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1453 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.