Decomposition of Complete Graphs Into Paths of Length Three and Triangles

Abstract

Let $P_{k+1}$ denote a path of length $k$ and let $C_k$ denote a cycle of length $k$. A triangle is a cycle of length three. As usual, $K_n$ denotes the complete graph on $n$ vertices. It is shown that for all nonnegative integers $p$ and $q$ and for all positive integers $n$, $K_n$ can be decomposed into $p$ copies of $P_4$ and $q$ copies of $C_3$ if and only if $3(p+q)=e(K_n)$, $p\ne 1$ if $n$ is odd, and $p\ge \frac{n}{2}$ if $n$ is even.