Introduction

It is natural to ask when a complete graph admits a decomposition into cycles of some fixed length. Since the existence of such a decomposition requires the degrees of the vertices to be even, the complete graph must have an odd number of vertices. However, this question can be extended to graphs with an even number of vertices by removing a 1-factor. The question then becomes the following: When does K_n or K_n - I, whichever is appropriate, admit a decomposition into cycles of length m, where m is fixed? There are two obvious necessary conditions, namely, that $3 \le m \le n$ and that m must divide the number of edges in either K_n or K_n - I. There is not one example known where these necessary conditions are not also sufficient.

There have been many articles discussing this question, as well as several surveys [4,5,8]. For the case of n odd, it follows from [4,10] that for m even, if the necessary conditions are sufficient for n in the range $m \le n \le 3m$, then they are sufficient for all $n \ge m$. The same result holds true for m odd [7]. For the case of n even, it was shown in [1] that a similar result holds for K_n - I with m even, and they suggest that the results in [7] will extend to K_n - I with m odd. In [12], it was shown that if n is odd and large enough, then the necessary conditions are also sufficient. Also, in [2], it was shown that the necessary conditions are sufficient for all $m \le 50$ and n odd. Using the results of [6,11], it is easy to show that the necessary conditions for a decomposition of K_n - I into cycles of even length m are sufficient if the number of edges in K_n-I is an even multiple of m. Next, in [1], it is shown that the necessary conditions are sufficient for a decomposition of K_n - Iinto cycles of even length m when n is divisible by 4, the number of edges in K_n - I is an odd multiple of m, and the congruence class of n modulo m lies between m/2 and m. In this paper, we will prove the following two results.

Theorem 1.1   For positive even integers mand n with $4 \le m \le n$, the graph K_n - I can be decomposed into cycles of length m if and only if the number of edges in K_n - I is a multiple of m.

Theorem 1.2   For positive odd integers mand n with $3 \le m \le n$, the graph K_n can be decomposed into cycles of length m if and only if the number of edges in K_nis a multiple of m.

Thus, it remains to show that K_n or K_n-I, whichever is appropriate, can be decomposed into cycles of length m whenever n and m have opposite parity.