1 · The essentials
Imagine a network of points joined by links, with no link from a point to itself and no repeated link between two points. The goal is to divide all its links into closed loops and individual links. Each loop must return to its starting point without visiting any other point twice, and every link must belong to exactly one piece. The main result says that a network with points always needs at most pieces, where is one fixed constant that works for every such network. This bound holds even when the network has many links. The result resolves the Erdős–Gallai cycle-decomposition conjecture positively and has a Lean formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine sorting a collection of connecting road segments into round trips and leftover individual segments. Every segment must be assigned exactly once, and each round trip avoids revisiting a junction except to finish where it started. The image captures the sorting task, but the result concerns abstract networks rather than the details of real roads.
Why it matters
The bound depends linearly on the number of points, even for dense networks. It therefore gives a uniform guarantee on how many pieces are needed, rather than a bound that simply counts all the links. The supplied source identifies this as a positive resolution of the Erdős–Gallai cycle-decomposition conjecture.
2 · Going further
Precisely, for every finite simple undirected graph with vertices, its edge set can be partitioned into at most pieces, each of which is either a simple cycle or a single edge. Here is an absolute constant: the same constant applies to every graph in the stated class. A partition requires that the pieces cover all edges without sharing any edge; the requirement is about edges, not about assigning vertices to separate pieces.
The supplied main manuscript, “A linear cycle-and-edge decomposition of every graph,” states this result and identifies it as resolving the Erdős–Gallai cycle-decomposition conjecture positively. The main result has a Lean formalization. The supplied abstract does not describe the argument or its main construction, so no proof strategy can be extracted from it. Only this main manuscript is supplied; no companion manuscripts or relationships among them are described.
Useful notions
- Vertices and edges of a graph
- Finite simple undirected graphs
- Simple cycles
- Partitions of a set
- Linear bounds and absolute constants
What was known before / what is new
Before
The source presents the linear cycle-and-edge decomposition statement as the Erdős–Gallai cycle-decomposition conjecture. It supplies no earlier bounds, dates, or account of partial results.
New
The main result establishes a bound of pieces for every finite simple undirected graph on vertices, with one absolute constant . The permitted pieces are simple cycles and single edges. The source reports a positive resolution of the conjecture, and the main result has a Lean formalization.
Limits and assumptions
The stated theorem applies to finite simple undirected graphs; the supplied text makes no claim about other graph classes. Single edges are allowed alongside cycles, so this is not a cycles-only decomposition. Neither a numerical value for nor an algorithm for finding the partition is supplied. The Lean-formalized scope is the main cycle-and-edge decomposition result; no additional results or remaining open questions are described.
Mini glossary
- Finite simple undirected graph —
- A network with finitely many vertices, whose edges have no direction, never join a vertex to itself, and occur at most once between any pair of vertices.
- Simple cycle —
- A closed sequence of edges that returns to its starting vertex without repeating any other vertex.
- Edge partition —
- A division of the edge set into pieces so that every edge belongs to exactly one piece.
- Absolute constant —
- A fixed constant that does not depend on the graph or its number of vertices.
- Linear bound —
- An upper bound of the form , with a fixed constant multiplying the number of vertices.
Keywords : Graph decomposition · Simple cycles · Erdős–Gallai conjecture
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
A linear cycle-and-edge decomposition of every graph
24/09/2026We 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.