The Setting
Let be a finite simple graph with vertex set , and let . The edge set always splits into paths, for instance into its single edges, and then a vertex of degree is an end of of the paths. The question is whether can be partitioned into paths so that no vertex is an end of more than two of them, with at most paths in all.
Paths and Endpoint Load
A path of positive length in is a sequence of distinct vertices of with and for ; its ends are and , and its edge set is .✦
For paths in , the endpoint load of a vertex of is the number of indices for which is an end of : (1)
An endpoint path partition of is a family of paths of positive length in with (2)✦ Write for the set of endpoint path partitions of .
The Claim
Theorem 1 (Corollary 2.2). Let be a finite simple graph. Then (3)✦ In particular, for every and every graph on the vertex set , (4)✦
What Is Checked
The claim (3) is stated over a finite simple graph, the paths of positive length in it, the endpoint load (1) of a family of such paths and the endpoint path partitions (2) built from them; (4) is stated over the graphs on the vertex sets , .