Linear partitions into cycles and edges

Source and verification

This article explains family 181 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Edge partitions into cycles

A cycle here is simple and has length at least three. An edge partition assigns each edge to exactly one part. The parts may share vertices, but may not share edges. Allowing single-edge parts is necessary because a forest has no cycles.

Manuscript claim

There is an absolute constant $C$ such that every finite simple graph on $n$ vertices has an edge partition into at most $Cn$ cycles and single edges. (OpenAI, 2026)

The empty partition is allowed for an edgeless graph. The statement does not identify the optimal constant. Its linear order is necessary: a tree on $n$ vertices requires $n-1$ singleton parts.

A cover by possibly overlapping cycles would be weaker. Deleting repeated edges from such a cover can break a cycle into many paths, so an economical cover does not automatically produce an economical partition.

🏷️ The Eulerian consequence

Call a graph Eulerian when every vertex has even degree, without requiring connectedness. The claimed theorem implies an edge partition of every Eulerian graph into at most $Cn$ cycles alone.

Indeed, remove the cycle parts from the supplied partition. The remaining singleton edges form a graph of even degrees, because deleting a cycle changes each degree by zero or two. Every nonempty finite even graph contains a cycle. Repeatedly removing such cycles exhausts the remainder, using at most one cycle per remaining edge. If the original partition had $r$ cycles and $s$ singleton edges, the final count is at most $r+s\le Cn$.

Every cycle-only decomposition needs at least $\Delta (G)/2$ cycles, since one cycle uses at most two edges at a fixed vertex. The manuscript also records a consequence attaining this bound up to $\delta n$ under a uniform lower density condition on all sufficiently large cuts. That additional hypothesis is not part of the general linear theorem.

🏷️ The cost of repeated scales

The proof decomposes a graph across successively smaller scales

$$D_j=n^{(0.95{)}^j}.$$

At a scale $D$, a small collection of long cycles is removed and the remaining edges are assigned to boxes with at most $D^{1.02}$ vertices. Boxes can overlap in vertices, but each original edge keeps a unique assignment. Their total vertex count increases by only a factor $1+O(1/\log D)$.

Within a box, the source extracts disjoint expanding pieces: every cut has many crossing edges relative to its smaller side. The remainder has lower average degree and is sent to the next scale.

Paying a cost proportional to the whole graph order at every scale would accumulate an unwanted iterated-logarithm factor. The manuscript instead chooses one layer whose total expanding-piece order can pay for an entire prefix of the decomposition, including a fixed gap of later scales.

🏷️ Folding vertices and reserving routes

The selected expanding pieces serve two purposes. They can themselves be decomposed at linear cost apart from small residual graphs, and they contain reserved edges for routing paths later.

After the gap in scales, unprocessed edges lie in much smaller boxes and are sparse. Low-degree vertices in suitable intersections are paired and identified. This folding reduces the number of vertices in the quotient graphs, creating the savings needed for induction.

Some troublesome edges are first separated into paths, whose remnants are closed using reserved routes. Further simplification after identification discards only linearly many singleton edges. The degree control applies to the union of all relevant batches inside an earlier box, so the routing load does not increase merely because the number of batches increases.

Every quotient edge retains one original representative. This bookkeeping prevents a quotient decomposition from using an original edge twice or leaving it unassigned.

🏷️ Lifting a quotient cycle without self-intersections

A quotient cycle can enter an identified vertex through one member of a pair and leave through the other. To lift it, insert a reserved path between those two original vertices.

Edge-disjoint routing alone is not enough to make the lift a simple cycle. Two inserted routes in the same cycle could meet at an interior vertex, or a route could pass through a representative endpoint. The source’s routing lemma excludes both problems: interiors avoid representative endpoints and are pairwise disjoint within each lifted cycle. Routes belonging to different cycles may share vertices while remaining edge-disjoint, which is permitted by the theorem.

This distinction is why vertex saving and cycle lifting must be designed together. Arbitrary contractions followed by arbitrary connecting paths would not preserve the type of decomposition.

🏷️ Closing the amortized induction

Let $S$ be the total order of the selected expanding layer. In the principal case, the work outside recursive calls costs $O(S+n/\log D)$ parts. Quotient orders sum to at most

$$n-S/3+O(n/\log D),$$

and small-residue graphs have total order at most $S/100$. For a sufficiently large induction constant, the saved fraction of $S$ pays for the work charged to that layer.

To absorb the remaining overlap error, the proof strengthens the induction to $C\varphi (n)n$, where, for $n>1$,

$$\varphi (n)=\max \left\{\frac{1}{2},1-\frac{1}{\sqrt{{\log }_{2}n}}\right\}.$$

The recursive graphs have size at most $D^{0.30}$. Their smaller value of $\varphi$ supplies a gain of order $1/\sqrt{\log D}$, larger than the $1/\log D$ overlap cost. Small and terminal cases are treated separately. This quantitative saving is the mechanism that removes the cost of the number of scales.

🏷️ Key steps and proof outlines

One layer pays for an entire prefix

Let $S_j$ be the total order of the expanding pieces extracted at scale $j$, with finitely many nonzero terms. The induction fixes $K=200$ and $P_0=4(K+1)$. Its prefix-selection lemma finds $i$ such that

$$\sum _{j=0}^{i+K}{S}_j\le P_0{S}_i.$$

Proof outline. Start at the first positive term and maintain ${\sum }_{j\le i}{S}_j\le 2(K+1)S_i$. If the desired bound fails, the next $K$ terms sum to more than $2(K+1)S_i$, so their largest value $M$ exceeds $2S_i$. Move to an index $i^{\prime }$ attaining it. Then

$$\sum _{j\le i^{\prime }}{S}_j\le 2(K+1)S_i+KM<(2K+1)M\le 2(K+1)S_{i^{\prime }}.$$

The invariant persists, and finite support forces termination. This is an actual amortization argument: one selected layer controls the cost of all earlier layers and a fixed later window. (OpenAI, 2026)

Routing uses separate resources for edges and team interiors

A quotient cycle creates demands to connect original vertices that were identified during folding. Give all demands belonging to that one quotient cycle the same team. The routing lemma requires all routes to be edge-disjoint, and routes in one team to have disjoint interiors. A demand also has a forbidden set containing representative endpoints it must avoid internally.

Encode a candidate path by its graph edges and by tokens $(v,c)$ for each interior vertex $v$ and its team $c$. Two selected paths sharing an edge compete for the same edge resource. Two paths sharing an interior vertex compete only if they belong to the same team. Thus disjoint representatives in this resource hypergraph enforce exactly the needed conditions.

For a router of order $r$ and cut expansion $h$, the source sets

$$g=\lceil 8(r/h)\log (2r)\rceil ,\ell =2g(1+\lceil \log r\rceil ).$$

If each vertex is an endpoint of at most $k$ demands, teams have size at most $b$, forbidden sets have size at most $z$, and $h\ge 64({\ell }^2(k+b)+z)$, routes of length at most $\ell$ exist. To prove the hypergraph matching condition, suppose a small matching blocks a demand family $I$. Its resources use at most $2{\ell }^2|I|$ graph edges and as many tokens. At least half the demands have a small team-token obstruction, and a maximal collection with disjoint endpoints contains at least $|I|/(4k)$ demands.

If both endpoint balls of one such demand grew beyond half the router, they would meet and supply a path avoiding all used resources, contradicting maximality. The source instead grows unions of balls while keeping each demand’s forbidden set attached to its own root, then alternates root-set reduction with further growth. Cut expansion forces one of these supposedly small balls to become too large. This closes the matching argument without incorrectly imposing one common forbidden set on every demand.

Count vertex savings using all batch occurrences

After the fixed scale gap, active low-degree sets inside expanding pieces are paired and folded. If $\Sigma$ counts their sizes across all indexed batches, the source proves

$$S_i-4n/w\le \Sigma \le S_i+Hn/w,w={\log }_{2}D,$$

where $H$ is an absolute overlap constant. The lower bound assigns one batch occurrence to each good piece vertex; the upper bound charges repeated occurrences to total batch overlap. The degree bound applies to the union of batches inside the earlier box, so the demand load does not grow with the number of batches.

A batch of order $|W|$ produces a quotient of order

$$q_W=|W|-\sum _R\lfloor |X_{W,R}|/2\rfloor \le |W|-\frac{1}{3}\sum _R|X_{W,R}|.$$

Hence total quotient order is at most $n-S_i/3+A_{1}n/w$, and each quotient has order at most $D^{0.30}$. The routers lift each quotient cycle to one simple cycle, with no extra part charge. Every consumed router edge is then removed before decomposing the remaining expanding pieces. This ledger ensures a partition of original edges throughout.

A slight improvement over linear induction pays for overlap

The remaining piece residues have total order at most $S_i/100$, while nonrecursive work costs at most $A_2(S_i+n/w)$. Apply induction with bound $C\varphi (n)n$, where $\varphi (n)=\max \{1/2,1-1/\sqrt{{\log }_{2}n}\}$. The coefficient charged to $S_i$ is at most

$$A_2+C/100-C/6=A_2-47C/300\le 0$$

for large enough $C$. For the overlap term, setting $\delta =1/\sqrt{0.30}-1$ gives

$$\varphi (n)-\varphi (D^{0.30})\ge \delta /\sqrt{w}.$$

This gain dominates the overhead $O(1/w)$ above a fixed scale cutoff. The total quotient order may even exceed $n$ slightly; the improved induction potential pays for that excess. Small scales are handled separately. These two savings remove any dependence on the number of decomposition levels.

See Also

• Barnette’s conjecture concerns one spanning cycle under planar structural assumptions.
• Thin trees also preserves a combinatorial object through repeated reductions with controlled accumulated loss.

🏷️ Manuscripts and verification scope

• A linear cycle-and-edge decomposition of every graph — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects one universal linear bound for all finite simple graphs, including edgeless and small cases, without an optimal constant. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A linear cycle-and-edge decomposition of every graph.