Erdős–Gallai cycle decomposition conjecture

Take a triangle and attach one extra link from one corner to a fourth dot. Its four links split into two pieces: the triangle's closed loop and the extra link by itself. Every link belongs to exactly one piece.

The question concerns any finite simple graph: a network of dots with no self-links and at most one link between each pair. Can its links always be split into closed loops and single links using at most a fixed multiple of the number of dots? The same fixed multiplier must work even as the network grows.[1]

The goal is to organize every edge of a finite simple graph into a small number of nonoverlapping closed loops and leftover single edges. A triangle with a pendant edge needs one cycle plus one single edge. Erdős–Gallai asks whether a fixed multiple of the vertex count always suffices for all such graphs.

Write $n$ for the number of vertices. One absolute constant $C$ must bound the number of pieces by $Cn$. A cycle has no repeated vertices except the closing return, and the pieces form an edge partition: every edge belongs to exactly one piece. Merely covering edges, allowing the same edge in several cycles, is a weaker requirement.

A vertex's degree counts its incident edges. Whether those degrees are even or odd gives a useful entry into the structure. Each cycle contributes an even number of incident edges at every vertex it meets. In the triangle-and-tail example, the attachment vertex and the tip have odd degrees; removing the single tail edge makes every remaining degree even. Even-degree graphs admit cycle decompositions, but that alone does not bound how many cycles are required.

The cited proof repeatedly extracts cycles and organizes remaining edges into subgraphs with an expansion property: sets of vertices still reach many outside vertices after some edges are removed. Applying the process again to the leftover graph rapidly reduces its average degree, the average number of edges incident to a vertex. That iterative reduction yields the extra iterated-logarithm factor in the general bound.[1]

The best checked general bound still has an extra growing factor.[1]

The checked general bound is $O(n\log^{*}n)$. Here $\log^{*}n$ counts repeated base-two logarithms needed to reduce n to at most one. That factor is unbounded, so the bound does not give the fixed-multiple guarantee $O(n)$. This is a decomposition problem, distinct from Erdős–Gallai results about degree sequences or cycle lengths.[1]

A network can have far more links than dots: ten dots can support 45 links. Grouping many links into loops asks whether this apparent complexity has a compact structural organization. The goal counts pieces, so it concerns organization rather than a guarantee about the number of bits needed to store the network.[1]

A graph may have on the order of $n^{2}$ edges, yet the conjecture would organize them into only on the order of $n$ pieces. This asks whether cycles capture much of a dense graph's structure even without regularity or randomness assumptions.

The connection with Euler's parity criterion is substantive: it separates the ability to decompose at all from the ability to do so economically. The cited work also develops ways to find paths and preserve expansion while removing edges. Those tools address how local connectivity can survive during a global decomposition, a broader issue than the numerical bound alone.[1]