In this section, we prove Theorem 1.1, that is, we are interested in
proving that the graph *K*_{n}-*I* can be decomposed into
cycles of length *m* when *m* and *n* are even and
.
The preliminaries have
been completed for the proof except for the
basic way in which we wish to view the graph *K*_{n}-*I*. We present this,
along with a lemma, and then proceed to the proof of the result.

The preceding definitions imply that the graph *K*_{n} - *I* can be thought
of as the join of a circulant
graph of order *n* - 2 with
,
that is,
*K*_{n} - *I* = *H*(*n*;*A*),
where
.
Thus the edges of length (*n*-2)/2in the circulant together with the edge *uw* make up the edges of the
1-factor *I*.

PROOF.Label the vertices of the subcirculant with
.
We have
if and only if .
Let
denote the permutation
.
If *L* is any subgraph of
*H*(*n*;*A*), then
is defined as
.

Let *P* be the trail of length
given by

Note that

Thus, we can form a cycle *C* of length *m* by taking

From the above remarks, it follows that is a partition of the edge set of

We now present the proof of the first main theorem.

PROOF OF THEOREM 1.1.
Let *m* and *n* be positive even integers with
.
As mentioned in the introduction, if
*n*(*n*-2)/2 is an even multiple of *m*, then using [6,11] it is
not difficult to show that *K*_{n} - *I* can be decomposed into *m*-cycles.
To do so, we think of *K*_{n}-*I* as the wreath product
,
that is, replace every vertex of *K*_{n/2} by a copy
of
and every edge of *K*_{n/2} by a copy of *K*_{2,2}.
A path *P* of length *m*/2 in *K*_{n/2} becomes
in *K*_{n}-*I*, and this graph can be decomposed into two cycles of length
*m* by the main result of [6]. The proof is completed by using
one of the main results of [11] to observe that *K*_{n/2} can be
decomposed into paths of length *m*/2.

Because of the preceding paragraph, we may assume that *n*(*n*-2)/2 is
an odd multiple of *m*. Next, by Lemma 2.3, we may
also assume that *n* < 2*m*, say *n*=*m*+*r* for some positive integer
*r* with
.
Now if *r*=0, we are done
by a construction of Walecki given in [9]. Thus, we assume
that 0 < *r* < *m*. We have
seen that
implies that
,
and since *n*(*n*-2)/2 is an odd multiple of *m*,
Lemma 2.4 implies that *r*(*r*-2)/2 is an even multiple of *m*.

Let
and label the vertices of the graph
*H*(*n*;*A*) with
,
where *u* and *w* are the
two vertices of
(see Definition 3.2).
Note that the edge joining *u*_{i} and *u*_{j} has length *j*-*i* or length
*i*-*j* depending on which lies between 1 and (*n*-2)/2 modulo *n*-2.
The proof of Theorem 1.1 proceeds as follows.
Suppose that *B* is a subset of *A* such that
,
and
that we can decompose the circulant
into *m*-cycles.
Then since
and
the graph *H*(*n*;*A*-*B*) can be decomposed into *m*-cycles by Lemma
3.4, it follows that we have a decomposition of *H*(*n*;*A*)into *m*-cycles. Thus, the rest of the proof consists of determining
a convenient set *B* of *r*/2 lengths such that the circulant
can be decomposed into *m*-cycles.

By Lemma 2.4, we know that *r* is congruent to 0 or
2 modulo 8, and thus the proof now breaks into these two cases.

CASE 1. SUPPOSE THAT *r* = 2^{e}*a* where *a* is odd and .
Thus
*r*(*r*-2)/2=2^{e}*a*(2^{e-1}*a*-1). Since *m* divides *r*(*r*-2)/2 evenly,
we have that *m*=2^{d}*a*'*b*', where ,
,
and
.
Then

Partition the vertices of the circulant

Let
,
where
is the permutation
from the proof of Lemma 3.4. Since
implies
that
,
the vertices of *P*_{0,1} are
distinct from the vertices of *P*_{0,0} except for ,
which is the
last vertex of *P*_{0,0} and the first vertex of *P*_{0,1}. Similarly,
the paths

are vertex-disjoint except that the path

The definition of *P*_{0,0} does not make sense when
2^{d-2}*a*'+2=1,
that is, *d*=2 and *a*'=1. In this case let

Let
*b*=*r*/(2^{d+1}*a*') = 2^{e-d-1}*a*/*a*'. If *b* > 1, then obtain the path
*P*_{1,0} by adding
to the subscripts of the even vertices of
*P*_{0,0}, that is,

Next, obtain the paths by letting powers of act on

Similarly, for each *j* with
,
obtain the path *P*_{j,0} by
adding
to the subcripts of the even vertices of *P*_{0,0}.
Then the paths
are obtained
by letting powers of
act on *P*_{j,0}.
Note here that *P*_{j,i} begins at the last vertex of *P*_{j,i-1} for
and the last vertex of
*P*_{j,b'-1} is *u*_{0}.
Hence
is an
*m*-cycle and the lengths of the edges of *C*_{j} are
.

For
,
let *B*_{j} denote the set of lengths that *C*_{j}uses, that is,
.
Let
.
Now the longest edge in *B* has length
.
Since
2^{e}*a* < 2^{d}*a*'*b*' implies that
,
it
follows that

Therefore, the lengths of

is a partition of the edge set of the circulant into

CASE 2. SUPPOSE THAT *r*=8*k*+2 for some nonnegative integer *k*. In this case we have
*r*(*r*-2)/2 = 8*k*(4*k*+1) = 2^{e}*a*(4*k*+1) where 2^{e}*a*=8*k*, *a* is odd, and
gcd(*a*,4*k*+1)=1. Then *m*=2^{d}*a*'*b*', where
,
,
and
.
Let *r*/2=*bb*'. Then

Let and note that . The proof now breaks into two subcases depending on the congruence class of

SUBCASE 2.1. SUPPOSE THAT *b*'=1 implies that
which is a contradiction.
Let
and note that *s* is odd. Consider the walk
*P*_{0,0} defined by

Since
,
we have that the vertices of
*P*_{0,0} are distinct so that *P*_{0,0} is a path. In the case that
*s*=3, we have *b*'=5 and ,
and
*P*_{0,0}=*u*_{-3},*u*_{0},*u*_{2},*u*_{-2},*u*_{3}.
Observe that the lengths of the edges of *P*_{0,0} are
.
Obtain the path *P*_{0,1} as before, that is,
.
Since
,
the paths *P*_{0,0} and
*P*_{0,1} are vertex-disjoint. Join the
first vertex of *P*_{0,1} to the last vertex of *P*_{0,0} and note that
this edge has length 1.

Again, let the powers of
act on *P*_{0,0} to obtain the paths
*P*_{0,0}, *P*_{0,1}, ,
*P*_{0, 2da'-1}. Form the *m*-cycle *C*_{0}by joining the last vertex of *P*_{0,i} to the first vertex of *P*_{0,i+1}for
and joining the last vertex of
*P*_{0,2da'-1}to the first vertex of *P*_{0,0}.
Necessarily, these edges all have length 1. Let
.

If *b* > 1, then obtain the path *P*_{1,0} from *P*_{0,0} by subtracting
from the subscript of the first vertex and adding
to the
subscripts of the remaining odd vertices of *P*_{0,0}, that is,

Then the lengths of the edges of

Similarly, for
,
obtain the path *P*_{j,0} from *P*_{0,0}by subtracting
from the subscript of the first vertex and adding
to the subscripts of the remaining odd vertices of *P*_{0,0}.
Again, letting the powers of act on *P*_{j,0}, we form the *m*-cycle *C*_{j} by joining
the last vertex of *P*_{j,i} to the first vertex of *P*_{j,i+1} for
and joining the last vertex of
*P*_{j,2da'-1} to
the first vertex of *P*_{j,0}. Observe that these edges have length
and thus the cycle *C*_{j} has edges with
lengths
.

Let
for
,
and let
Then the longest edge of *B* has length either
or
.
Now *r*= 2*bb*' and
*m* = 2^{d}*a*'*b*', and since *r* < *m*, we have that
2*b*< 2^{d}*a*'. Thus,
.
Therefore, the lengths
are all distinct. Next,

so that

is a partition of the edge set of the circulant into

SUBCASE 2.2. SUPPOSE THAT *P*_{0,0} be the path defined by

Note that

and note that

There are two special cases that must be considered. When *b*'=7, let

When

If *b* > 1, then obtain the path *P*_{1,0} by adding
to the
subscripts of the even vertices of *P*_{0,0}, that is,

Next, obtain the paths by letting powers of act on

Similarly, for each *j* with
,
obtain the path *P*_{j,0}by adding
to the subscripts of the even vertices of *P*_{0,0}.
Then the paths
are obtained by
letting powers of
act on *P*_{j,0}. For
,
let
denote the collection of paths
and *B*_{j} denote the set of lengths that
uses, that is,

Observe that has

Recall that
is the initial vertex of *P*_{j,i} and
is the terminal vertex of *P*_{j,i} for
and
.
Now we shall link the paths of
to
form an *m*-cycle. We shall use Hamilton cycles in an auxiliary
circulant graph *G* to do so. Let the vertices of *G* be labeled
.
Suppose we are given a Hamilton cycle
*C* in *G*. Arbitrarily orient the cycle *C* to obtain a Hamilton
directed cycle
.
If there is an arc from *v*_{i} to
*v*_{k} in
(of length *k*-*i*), then insert an edge,
necessarily of length
,
from the terminal vertex of
*P*_{j,i} to the initial vertex of *P*_{j,k}. If we do this for each
arc in
,
it is easy to see that the paths of
are joined together to form an *m*-cycle. Furthermore,
since the edge from the terminal vertex of *P*_{j,i} to the initial
vertex of *P*_{j,k} has different length, namely
,
than
the edge from the terminal vertex of *P*_{j,k} to the initial vertex of
*P*_{j,i}, we can use the reverse orientation
of
to link the paths in another collection
,
,
into an *m*-cycle. Observe that all the edges used to link
together the paths have lengths congruent to
modulo
and thus none of them have been used in the
construction of the families
.

There are several points we need to consider. First, if a Hamilton cycle
in *G* uses exactly one length for its edges, then it is easy to see that
it can be used to link together the paths of some
to form
an *m*-cycle and, in doing so, we use exactly one length in *H*. However,
if a Hamilton cycle in *G* uses different lengths for its edges, then
using either orientation to link together paths of some
,
results in some edges of lengths congruent to
modulo
not
being used. We handle this as follows.

J.-C. Bermond, O. Favaron and M. Maheo [3] proved that any connected
circulant graph of degree 4 can be decomposed into two Hamilton cycles. So
we choose two lengths *s*_{1} and *s*_{2} in *G* such that
gcd
(*s*_{1},*s*_{2})=1, which guarantees that the circulant graph with connection
set
is connected. We
decompose it into two Hamilton cycles and orient each of them in the
two possible ways. We then use these four oriented cycles to form four
*m*-cycles in *H*. This then uses all the required edges in *H* of
lengths congruent to
modulo
corresponding
to the edges used in the Hamilton cycles. Second, when we are left with
1 or 3 families
to link together, we use one or two
Hamilton cycles from *G* with edges of the same length to complete the
linking process.

We now must show that there are enough edge-disjoint Hamilton cycles
in the auxiliary graph *G* to make the above scheme work. Recall that
the number of vertices in *G* is 2^{d}*a*' and that 2^{d}*a*'>2*b*.
We now proceed depending on the number of families
to
link together. If *b*=1, then let
so that *G*is a (2^{d}*a*')-cycle. In this case, the length
is used in
*H* to link
into an *m*-cycle. If *b*=3, then *G* has at
least eight vertices so that there are at least two lengths *s*_{1} and
*s*_{2} relatively prime to 2^{d}*a*'. Then each of *s*_{1} and *s*_{2}generates a Hamilton cycle in
and
thus we can easily link together the three families of paths into
*m*-cycles. In this case, the lengths
,
and
are used in *H* to link
into *m*-cycles.

Finally, if *b* >3, then write
*b* = 4*q* + 1 or
*b* = 4*q* + 3 for some
positive integer *q*. Suppose first that
*b* = 4*q* + 1. Then
can be used to link
into an *m*-
cycle using the length
in *H*. Next take *q* successive
pairs
,
all of which generate
connected circulants, to obtain two Hamilton cycles in
,
for
,
to link together four
families at a time. Then the lengths
are used in *H*. If
*b* = 4*q* + 3, then find a second integer
relatively prime to 2^{d}*a*' to handle the two extra
families, and the lengths
and
are used in *H*.

Upon obtaining all the *m*-cycles as described above, we then let act on each *m*-cycle *C* according to
resulting in a decomposition of
into *m*-cycles. This completes the proof of Theorem 1.1.