Decomposition of complete graphs into paths and cycles of distinct lengths

Abstract

Let Pk be the path with k edges and Ck be the cycle with k edges. For r ≥ 3, we exhibit two decompositions of the complete graph K2r+3 into edge-disjoint paths and cycles: the first is of the form ⟨P3, P4, C5, C6, ..., C2r−1, C2r+1, C2r+2, C2r+3⟩ and the second ⟨P3, P4, P5, C6, ..., C2r−1, C2r+1, C2r+2, C2r+3⟩