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 \neq 1\) if \(n\) is odd, and \(p \geq \frac{n}{2}\) if \(n\) is even.