# 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 Kn or Kn - I, whichever is appropriate, admit a decomposition into cycles of length m, where m is fixed? There are two obvious necessary conditions, namely, that and that m must divide the number of edges in either Kn or Kn - 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 , then they are sufficient for all . 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 Kn - I with m even, and they suggest that the results in [7] will extend to Kn - 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 and n odd. Using the results of [6,11], it is easy to show that the necessary conditions for a decomposition of Kn - I into cycles of even length m are sufficient if the number of edges in Kn-I is an even multiple of m. Next, in [1], it is shown that the necessary conditions are sufficient for a decomposition of Kn - Iinto cycles of even length m when n is divisible by 4, the number of edges in Kn - 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 , the graph Kn - I can be decomposed into cycles of length m if and only if the number of edges in Kn - I is a multiple of m.

Theorem 1.2   For positive odd integers mand n with , the graph Kn can be decomposed into cycles of length m if and only if the number of edges in Knis a multiple of m.

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

Brian &
2000-01-20