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
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
,
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 *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
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} - *I*into 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.

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.