The Setting
Take a simple graph on a finite vertex set, with edge set . Its edges can be shared out among cycles and single edges of so that every edge is used exactly once, if only by taking each edge on its own; the question is how few cycles and edges suffice. Erdős and Gallai conjectured that for a graph on vertices, of them always suffice.
A cycle of is a closed walk in of length at least that passes through no vertex twice except that it ends where it starts; its edge set is the set of edges it traverses.
The Claim
Definition 1. Let be a graph. A part of is a set of edges of that is the edge set of a cycle of or consists of a single edge of : (1)✦ For an integer , a cycle-and-edge partition of into parts is a sequence of pairwise disjoint parts of whose union is .✦ The decomposition cost of is the least for which has a cycle-and-edge partition into parts✦. (2)✦
In the paper, the definition reads: a partition of into parts, each the edge set of a simple cycle or a single edge, where parts may share vertices but not edges.
What Is Checked
The parts in (1) and the cycle-and-edge partitions are defined for a simple graph on any vertex set, and the decomposition cost and (2) for a simple graph on a finite vertex set.