Decompositions of Complete Graphs Into Paths and Cycles

Abstract

Let $P_{k+1}$ denote a path of length $k$ and let $C_k$ denote a cycle of length $k$. As usual, $K_n$ denotes the complete graph on $n$ vertices. In this paper, we investigate decompositions of $K_n$ into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing $K_n$ into $p$ copies of $P_5$ and $q$ copies of $C_4$ for all possible values of $p\ge 0$ and $q\ge 0$.