In this section, we prove Thereom 1.2, that is, we are interested in
decomposing the complete graph *K*_{n} into cycles of length *m* when
*m* and *n* are odd positive integers and
.
As in Section 3, we begin by presenting the way in which
we wish to view the graph *K*_{n}.

The preceding definition implies that the graph *K*_{n} can be viewed as
the join of a circulant graph of order *n* - 1 with *K*_{1}, that is,
*K*_{n}
= *H*(*n*;*A*) where
.

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

Let *w* denote the last vertex of *P*, that is,

Form a cycle

Then is a partition of the edge set of

We now present the proof of our second main result.

PROOF OF THEOREM 1.2. Let *m* and *n* be positive odd integers
with
.
Recall that by a result given
in [7], it
is sufficient to prove the theorem for values of *m* and *n* with
.
Thus, we may write *n* as *n* = *m*+*r* or *n* = 2*m*+*r*where
.
Let
and label the
vertices of the graph *H*(*n*;*A*) with
,
where *u* is the vertex of *K*_{1} (see Definition 4.1). Let
denote the permutation
.
There
are two cases depending on whether *n* = *m* + *r* or *n* = 2*m*+*r*.

CASE 1. SUPPOSE THAT *N* = *M*+*R*. Clearly, if *r*=0, we
are done by the Walecki Hamilton decomposition of *K*_{n} found in [9].
Thus, we may assume that 0<*r*<*m*. Suppose *B* is a subset of *A* such
that |*B*| =*r*/2 and that we can decompose the circulant
into *m*-cycles. Since
and
since *H*(*n*;*A*-*B*) can be decomposed into *m*-cycles by
Lemma 4.2, we have a decomposition of *H*(*n*;*A*) into
*m*-cycles. Thus, our goal is to choose a convenient set *B* of *r*/2lengths. Since *m* and *n* are odd, it must be that *r* is even, say
*r* = 2^{e}*a*, with *a* odd. Since
,
we
also have that
.
Since
*r*(*r*-1)/2=
2^{e-1}*a*(2^{e}*a*-1), we may write *m* as *m* = *a*'*b*' where
and
.
Let *r*/2 = *a*'*c*.
Next,

We partition the vertices of into

SUBCASE 1.1. SUPPOSE THAT *P*_{0,0} of length *a*'-1 as follows when *a*'>7:

Observe that the lengths of the edges of

When *a*'=3, let
,
and when *a*'=7, let
.

If *c* > 1, then, for each
,
obtain the path
*P*_{j,0} from *P*_{0,0} by adding
to the subscripts of the
even vertices of *P*_{0,0}, that is,

and continue as before letting the powers of act on

For
,
let
denote the collection of paths
*P*_{j,0}, *P*_{j,1}, ,
*P*_{j,b'-1}. Then the set
consists of *c*(*a*'-1) lengths.
Also, the longest edge of
has
length
,
and it is easy to see that
.
Note also that
contains no length that is congruent to
modulo
as long as
(we handle this case separately). Thus, we may use
circulants of order *b*' to link each family
into an
*m*-cycle *C*_{j} as in Subcase 2.2
of the proof of Theorem 1.1. Then the collection

is a partition of the edge set of the circulant

If
and *a*'>3, let

For

In this case, *b*'=*r*-1 and if we express *b*' in the form *b*'=*a*'*t*+*s*,
,
we find that *a*'*b*'=*m* divides the number of edges in
*K*_{m+r} if and only if *s*=*a*'-1. Since *m* is odd, *t* must be odd.
Thus, *r*=*a*'(*t*+1) so that
*b*'=*a*'(*t*+1)-1 and *c*=(*t*+1)/2.

Let us examine the lengths of various linking edges arising from arcs
of Hamilton directed cycles resulting from the circulant graphs. If we
have an arc from *v*_{i} to *v*_{k}, then we would be joining the terminal
vertex of some *P*_{j,i} to the initial vertex of *P*_{j,k}. The length
of such a linking edges is
.
If the arc goes from
*v*_{k} to *v*_{i}, then the length of the linking edge is
.
So if *c*=4*q*, then we use Hamilton decompositions of the
degree 4 circulants
as before. Since
,
the lengths of the linking edges are smaller than (*n*-1)/2.
Similar arguments work for *c*=4*q*+1, *c*=4*q*+2 and *c*=4*q*+3.

SUBCASE 1.2. SUPPOSE THAT *a*'=1 implies that *m*<*r*, we may assume that .
First, suppose that
.
As in the case
of subcase
1.1, we obtain
*b*'=*a*'(*t*+1)-1, *c*=(*t*+1)/2 and *t* is odd. Let

Obtain the paths . by letting powers of act on

If *c* = 4*q*, then
.
Use the sets of paths
.
Note that the longest edge has
length
.
We use Hamilton directed cycles arising from
Hamilton decompositions of
,
,...,
.
These linking edges have length longer than
and less
than (*n*-1)/2 so that all lengths are distinct.

There is so much latitude that the other cases are easy to do too.
For example, if *c*=4*q*+1, use the sets of paths
,
the same linking scheme for 4*q* of the
families, and edges of length (*a*'+3)/2 to link together the other
family. The cases *c*=4*q*+2 and *c*=4*q*+3 can be done similarly.

Finally, suppose that
.
Let
and note that *t* is odd. Consider the walk *P*_{0,0} of length *a*'-1defined by

Since

If *c* > 1, then, for each
,
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}, that is,

and continue as before letting the powers of act on

Let
.
Then the longest edge
of *B* has length
or
.
We already
have seen that
and it is not hard also to see
that
.
Thus *B* consists of *r*/2 distinct
lengths. Therefore, the collection

is a partition of the edge set of the circulant into

CASE 2. SUPPOSE THAT *N* = 2*M* + *R*. In this case, *r*is odd and suppose first that *r*=1 so that
*n* = 2*m* + 1. Relabel the
vertex *u* of *H*(*n*;*A*) with *u*_{n-1}, and as before, for
,
the length of the edge *u*_{i}*u*_{j} is either *i* - *j* or *j* - *i*,
depending on which lies between 1 and (*n*-1)/2 modulo *n*. Let
.
Next, suppose that
(*m*-1)/2 is odd. Consider the *m*-cycle *C* given by

Then is a partition of the edge set of

As before, is a partition of the edge set of

Thus, we may assume that *r*>1. To complete the proof we extend the
method used to solve the preceding case in which *r*=1. We note that
this means the proof will be different from all previous cases because
we no longer can build two diametrically opposed symmetric paths which
are linked to form a cycle via one or two central vertices. Instead, we
now use (*r*-1)/2 lengths to generate *m*-cyles by breaking the *n*vertices into segments, and we use the remaining *m* lengths to form
a single *m*-cycle which is acted on by .

Let *r*=2^{e}*a*+1, *a*'|*a*,
*b*'|(2^{e}*a*+1), *m*=*a*'*b*' and *m*>*r*. Then
*n*=2*m*+*r*=*b*'(2*a*'+(2^{e}*a*+1)/*b*'). Chop the vertices into *b*' segments
each having
2*a*'+(2^{e}*a*+1)/*b*' vertices. Let
*c*=(*r*-1)/2*a*'=2^{e-1}*a*/*a*'.
We have

giving us a lower bound on the number of segments.

Write *c* in the form
.
Suppose *t*=0 and
(*a*'-1)/2 is odd. Let

The lengths of the edges of

We are going to use edges whose lengths are congruent to
modulo
as linking edges to form cycles. Thus, in forming *P*_{1,0}we do not want to use an edge of length
.
Let *P* be the
path obtained from *P*_{0,0} by adding *a*' to the subscripts
of all even vertices of *P*_{0,0}. The lengths of the edges used in *P*are
.
If
,
then let *P*_{1,0}=*P*. If
,
then
in *P* do not omit the vertex
*u*_{a'+(a'+1)/4}; instead, omit the
vertex which would lead to the edge of length
being
omitted. Since
is even, the omitted vertex is in the
interval from *u*_{0} to
and the last vertex in the interval
from *u*_{0} to
in the resulting path still is
*u*_{a'+(a'+1)/2}. This is the path *P*_{1,0}. Now
obtain
from *P*_{1,0} using powers
of
again. Observe that the paths
are mutually vertex-disjoint because
implies
.

In the special case that *a*'=3, we use
*P*_{0,0}=*u*_{0},*u*_{2},*u*_{-1} and
*P*_{1,0}=*u*_{0},*u*_{4},*u*_{-1}.

Let *P*_{2j,0} be obtained by adding
to the subscripts of the
even vertices of *P*_{0,0}, and obtain
from
*P*_{2j,0} in the usual way. Finally, obtain
*P*_{2j+1,0} by adding to the subscripts of the even vertices of *P*_{1,0}, and obtain
as before. Let
.
None of the paths use edges whose lengths are
congruent to
modulo .
We use edges of these lengths
to link the paths of
together to form *m*-cycles based on
Hamilton directed cycles arising from Hamilton decompositions of
circulants of order *b*' and degree 4 as done for earlier cases. Use
the circulant
for the collection of paths
and
,
.

Let us verify that all the lengths employed are distinct. The length of the longest edge is , and the number of vertices is . Thus, all edge lengths are distinct.

We now show that we can use the remaining *m* lengths to form an
*m*-cycle. Arrange the remaining lengths in ascending order
.
Since the longest length already used is
and (*r*-1)/2 lengths have been used, the lengths
consist of successive integers from
through (*n*-1)/2, where
.
Start a path *P* according to

noting that

and so on until reaching . Notice that

This leaves us with the problem of what to do when
.
The first step is to let
be the odd length
edge we delete in forming *P*'.
Currently, *P*' ends with
*u*_{y-1},*u*_{-z},*u*_{y}, the edge
*u*_{y-1}*u*_{-z}has length (*n*-5)/2, and the edge *u*_{-z}*u*_{y} has length (*n*-3)/2.
Perform the following alteration of *P*'. From *u*_{y-1} reverse the
order of the lengths encountered to (*n*-1)/2, (*n*-3)/2, (*n*-5)/2and since there are two choices for the edge of length (*n*-1)/2, the
altered path terminates at either *u*_{-z-3} or *u*_{-z-4}. If either
*z*+3 or *z*+4 equals
,
then we close the path to an
*m*-cycle with an edge of length
.
If
,
then start the alteration of *P*' at *u*_{y-2}.
It is then possible to have the altered path terminate at either
*u*_{-z-5} or *u*_{-z-6}. If either *z*+5 or *z*+6 equals
,
then we complete to an *m*-cycle as before. We need to show
we can achieve an alteration of *P*' so that it terminates at
.
We have

edges whose lengths are consecutive integers from through (

Notice that
implies
are successive integers in the sequence
.
This in turn implies a gap of length at least (*a*'+3)/2in the vertices having negative subscripts when forming the *m*-cycle.
On the other hand, when
,
we have
and
.
Thus, the first vertex employed in
the *m*-cycle which has a negative subscript is
*u*_{-(a'+3)/2}. In
either case, it is easy to see that

using the facts

the longest subpath which would need to be reversed has length less than . Observe that

because , and

If *c*=4*k*+1, we link the paths of
to form an *m*-cycle
using edges of length
.
We then use Hamilton
decompositions of

to handle the families . The remaining

For *c*=4*k*+2, we link the paths of
and
to form two *m*-cycles using edges of lengths
,
respectively. The remaining families of paths and the resulting *m*lengths are done as before. Finally, for *c*=4*k*+3, use the lengths
and
to link the paths
,
and
,
respectively. Use Hamilton decompositions
of

for . The remaining

This leaves us with the case that (*a*'-1)/2 is even. It is rather
similar to the case when (*a*'-1)/2 is odd so that we outline how to do it.
Let

The path

ACKNOWLEDGEMENT

The authors would like to thank Mateja Sajna for her careful
reading of an earlier version of this paper which led to several
improvements.