Partitioning every graph into only linearly many cycles and edges

← All digests

Family 181 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

A dense graph may have quadratically many edges. Can all of them be organized into only linearly many simple cycles, with individual edges used for the parts that cannot join a cycle?

Single edges are necessary: a tree has no cycle at all. The Erdős–Gallai cycle decomposition conjecture says this allowance is enough. Every graph on $n$ vertices should have an edge partition into at most $Cn$ cycles and single edges for one universal constant $C$.

The manuscript claims the conjecture. Earlier general bounds had reduced the extra factor from a logarithm to an iterated logarithm. The new argument claims to eliminate that last growing factor by saving vertices during recursion and using those savings to pay for the work of joining paths into cycles.

2. Background and essential definitions

All graphs in the main theorem are finite, simple and undirected. A simple cycle visits distinct vertices before returning to its start and has length at least three.

An edge partition assigns every graph edge to exactly one part. Here each part must be either the complete edge set of a simple cycle or one individual edge. Different parts may share vertices; they may not share edges.

This differs from an edge cover by cycles and edges, where repeated use of the same edge is permitted. A small cover need not become a small partition when repetitions are removed: cutting edges out of a cycle can break it into many paths.

Write $e(G)$ for the number of edges and $\Delta(G)$ for the maximum vertex degree. A graph is Eulerian in this article when all vertex degrees are even; connectivity is not required. Such a graph has a decomposition into cycles, but controlling their number is a further problem.

The notation $O(n)$ means at most a constant multiple of $n$, with the constant independent of the graph. The earlier term $\log^*n$ is the number of successive logarithms needed to reduce $n$ to at most one. It grows extraordinarily slowly, but it is still unbounded. Removing it changes an almost-linear estimate into a uniform linear theorem.

3. Development history and previous partial results

The conjecture was recorded in the 1966 paper of Erdős, Goodman and Pósa, which distinguished edge-disjoint decompositions from unrestricted covers and gave an $O(n\log n)$ upper bound.

Conlon, Fox and Sudakov improved the general bound to $O(n\log\log n)$ in 2014. Their methods used sparse cuts and reserved edges to organize cycles across different density scales. Bucić and Montgomery subsequently reached

$$O(n\log^*n),$$

with the journal version appearing in 2024. Expansion, hypergraph matching and path-closing methods in that work form the principal starting point of the present manuscript.

Linear bounds were already known in important settings. Conlon, Fox and Sudakov proved them for graphs of linear minimum degree and, with high probability, for binomial random graphs. Korándi, Krivelevich and Sudakov obtained asymptotically sharp counts over a broad random-graph range.

For dense graphs, Girão, Granet, Kühn and Osthus obtained a bound of $(3/2+\delta)n$ for every fixed positive $\delta$, provided the minimum degree is a fixed positive fraction of $n$ and $n$ is sufficiently large. Akbari, Aloni, Beikmohammadi and Clow proved the bound $n-1$ for graphs of positive order and maximum degree at most four.

The unrestricted covering problem was easier: Pyber proved that $n-1$ cycles and edges cover every graph of positive order, and later work improved this when a cycle is present. Those results permit overlap and therefore do not settle the edge-partition question.

The new claim handles arbitrary mixtures of sparse regions, dense regions and highly unequal degrees, while preserving a unique assignment of every edge throughout the construction.

4. What the new manuscripts claim

The main theorem states that there is an absolute constant $C>0$ such that every graph $G$ on $n$ vertices has a partition

$$E(G)=E_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}E_m, \qquad m\leq Cn,$$

where each $E_j$ is either a simple cycle’s edge set or a singleton. The dotted union means the parts are disjoint.

The empty partition is allowed when the graph has no edges. Isolated vertices require no separate part. The same constant works for every graph size and every degree pattern.

The paper derives two cycle-only consequences. First, every Eulerian graph on $n$ vertices has a partition into at most $Cn$ cycles. To understand the deduction, remove the cycle parts from the main decomposition. The remaining single-edge graph still has even degrees and can itself be decomposed into cycles, using no more parts than the number of leftover edges.

Second, fix $\delta,p>0$. For sufficiently small $\varepsilon>0$ and sufficiently large $n$, an Eulerian graph satisfying

$$e_G(A,B)\geq p|A||B|$$

for every vertex partition into two sets of size at least $\varepsilon n$ has a decomposition into at most

$$\frac{\Delta(G)}2+\delta n$$

cycles. Here $e_G(A,B)$ counts crossing edges. This is a large-cut density condition, and the consequence uses a previously established equivalence in the dense-decomposition literature.

The maximum-degree term is unavoidable: each cycle can use at most two edges incident with a fixed vertex. Thus at least $\Delta(G)/2$ cycles are necessary, and the corollary approaches this lower bound up to a small linear error under the additional hypothesis.

5. Why the advance matters

Importance: 4/5. The claim establishes a longstanding universal decomposition principle. A graph with up to quadratically many edges can be described by only linearly many edge-disjoint cyclic pieces and isolated edge pieces, regardless of its irregularity.

The order of the bound is best possible. A tree on $n$ vertices requires $n-1$ single-edge parts. Certain complete bipartite examples require approximately $3n/2$ parts, so even the optimal universal leading constant cannot be read off from trees alone.

The advance is subtle because $\log^*n$ is tiny for any ordinary numerical input. Mathematically, however, a uniform linear bound demands a new accounting mechanism: work across arbitrarily many scales cannot repeatedly charge the full vertex set. The manuscript’s vertex-saving recursion is intended to supply that missing mechanism. Its Eulerian consequences also connect the general result with nearly optimal cycle counts in dense settings.

6. The main idea

Separate the graph by scales

A graph has strong cut expansion when every vertex set has many outgoing edges compared with its smaller side. Such regions are useful for routing paths: there are many ways to connect selected endpoints without consuming the same edges repeatedly.

The proof divides the graph into overlapping vertex regions with disjoint assigned edge sets. At each scale it removes a controlled collection of long cycles, extracts expanding pieces, and sends sparser residual graphs to smaller scales. The overlap in vertex counts must be carefully bounded even though the edges remain uniquely assigned.

Processing every expanding piece at every scale would recreate the unwanted logarithmic loss. Instead, the manuscript selects one layer whose total size can pay for a whole earlier portion of the decomposition.

Reserve routes before simplifying

Some edges in the selected expanding pieces are reserved for later connections. The remaining sparse regions are collected into batches. Many vertices have low total degree across the relevant batch, allowing them to be paired and identified.

Identifying two vertices reduces the order of the graph. This gives the induction a smaller problem, but it can create loops or parallel edges. The construction sets aside only a controlled linear number of such troublesome edges and records an original representative for every retained quotient edge.

The quotient graphs are then decomposed recursively. The saved vertex count is the resource that pays for the parts already completed and the edges set aside outside the recursive calls.

Lift quotient cycles back to real cycles

A cycle in the quotient may enter an identified vertex through one original member of the pair and leave through the other. To lift it back, those two original vertices must be joined by a reserved path.

The routing lemma chooses these paths edge-disjointly. It also keeps their interiors away from the representative endpoints and, within each lifted cycle, from one another. These conditions ensure that one quotient cycle becomes one simple original cycle, rather than a closed walk with repeated vertices.

This is why arbitrary contraction would not suffice. The identifications are coordinated with expansion and reserved routes from the beginning. The construction must retain both a smaller recursive graph and enough unused structure to undo its simplification.

Make the savings exceed the overhead

The recursive cost is not bounded merely by writing $Cn$ at every stage. The manuscript proves a slightly stronger estimate $C\phi(n)n$, where $\phi(n)$ approaches one slowly from below.

Smaller quotient graphs have a smaller value of this factor. That additional decrease absorbs the overlap and rounding costs left after the main vertex savings. The final bound is then at most $Cn$.

The overall strategy combines classical path decompositions, matching theorems for choosing disjoint routes, and a multiscale induction whose budget is tied to genuine reductions in vertex count.

7. Scope, limitations, and open questions

The theorem gives an unspecified universal constant, not the sharp leading constant. The examples requiring nearly $3n/2$ parts remain relevant to the finer optimization problem.

The graph is simple. Temporary quotient multigraphs are cleaned up internally, but that does not amount to a theorem with the same $Cn$ bound for arbitrary parallel-edge inputs. The definition of a cycle remains simple and of length at least three.

Single edges are permitted in the general conclusion. Removing that allowance requires an even-degree condition; otherwise some edges cannot belong to an edge-disjoint cycle decomposition. The Eulerian corollary makes this distinction explicit.

The near-$\Delta/2$ count requires the stated density condition across every sufficiently large vertex partition. It is not claimed for every Eulerian graph. Finally, the headline is an existence theorem and does not state an optimized practical algorithm for minimizing the number of parts.

8. Sources and further reading

The manuscript’s introduction gives the progression from logarithmic losses to the linear claim and carefully distinguishes covers from partitions. Its roadmap explains how reserved routes allow quotient cycles to be lifted without edge reuse.

The main immediate predecessor is Bucić–Montgomery’s decomposition paper. Akbari–Aloni–Beikmohammadi–Clow gives recent sharp results for restricted degrees and overlapping covers. M1’s bibliography identifies the original Erdős–Goodman–Pósa formulation, Conlon–Fox–Sudakov’s cycle-packing work, and the dense-graph equivalence used for the final corollary.

Source manuscripts

• M1. OpenAI, A linear cycle-and-edge decomposition of every graph (September 24, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.