The Setting
Let be a finite simple graph on vertices, with edge set . Its edges can be split into paths and cycles, each edge in exactly one part, and the question is how few parts such a split needs as a function of . Lovász’s theorem answers it.
Pieces and Partitions
A piece of is a path of positive length in or a cycle in ; for a piece , is its set of edges.✦ A path-or-cycle set of is a set of edges of that is the edge set of a piece of .✦
A path-cycle partition of with parts is a family of pairwise disjoint path-or-cycle sets of whose union is the edge set of : (1)
A decomposition of into pieces is a family of pieces of , no two of which share an edge, whose edge sets together make up : (2)
The non-isolated vertices of are those that lie on an edge of , and denotes their number.✦
The Claim
Theorem 1 (Lovász).
Every graph on vertices has a path-cycle partition whose number of parts satisfies (3)✦
Let be an integer and a graph with vertex set . Then has a path-cycle partition whose number of parts satisfies (4)✦
Every graph has a decomposition into pieces whose number satisfies (5)✦
In the paper, the result reads: the edges of a finite simple graph on vertices can be partitioned into at most paths and cycles.
For an integer , the bound of (3) and (4) is the bound .
What Is Checked
The claims (3) and (4) are stated over graphs and their path-cycle partitions, the second for graphs with vertex set for every , and (5) over decompositions into pieces and the number of non-isolated vertices.