The Setting
Let be a simple graph on vertices with edge set . The question is how few parts suffice to partition into edge sets of cycles and single edges. Taking each edge as a part gives parts, of order when is dense; the Erdős-Gallai conjecture asserts that a number of parts linear in always suffices, with a constant that does not depend on .✦
Cycles and Partitions
A cycle of is a closed walk in with and whose vertices are distinct; its edge set is . A cycle-or-edge set of is a set of edges of that is either the edge set of a cycle of or for a single edge of .✦
A cycle-and-edge partition of into parts is a sequence of cycle-or-edge sets of with (1)✦
The Claim
Theorem 1. There is a constant such that, for every integer , every simple graph on the vertex set has a cycle-and-edge partition into parts with (2)✦
In the paper, the result reads: there is an absolute constant such that, for every finite simple undirected graph with vertices, has a partition into at most parts, each of which is the edge set of a cycle or consists of a single edge.
What Is Checked
The claim (2) is stated over simple graphs on for every , and over their cycle-and-edge partitions (1), whose parts are edge sets of cycles and single edges.