The Setting
How few cycles and single edges does it take to partition the edges of a graph on vertices? Splitting into single edges takes of them, of order when is dense, and Erdős and Gallai conjectured that always suffice. Proposition 7.2, the inductive bound of §7, bounds this number linearly in .
Cycle-and-edge Partitions
A cycle-or-edge set of a graph is a set of edges of that is either the edge set of a cycle of or consists of a single edge of .✦ A cycle-and-edge partition of into parts is a sequence of cycle-or-edge sets of such that (1)✦
The decomposition cost of a graph on a finite vertex set is the least for which has a cycle-and-edge partition into parts.✦
The induction factor is the real function given by (2)✦ where is the logarithm to base .
The Claim
Theorem 1. There is a constant such that every graph on vertices satisfies (3)✦
In the paper, the result reads: there is an absolute constant such that every graph on vertices has an edge partition into at most cycles and single edges.
What Is Checked
The claim (3) is stated over all graphs on a finite vertex set, the empty vertex set included, with the least number of parts in a cycle-and-edge partition (1) of and the induction factor (2).