The Odd Case

In this section, we prove Thereom 1.2, that is, we are interested in decomposing the complete graph Kn into cycles of length m when m and n are odd positive integers and $n(n-1)\equiv 0({\rm mod}\ 2m)$. As in Section 3, we begin by presenting the way in which we wish to view the graph Kn.

Definition 4.1   Let $A\subseteq\{1,2,\ldots,(n-1)/2\}$, where n is a positive odd integer. Let G be the circulant graph of order n-1 with connection set $A \cup -A$, and u be an independent vertex that is not a vertex of G. Define $H(n;A)=G\bowtie \{u\}$, that is, $H(n;A)=G\bowtie{K_1}$, where the vertex of K1 is labeled u.

The preceding definition implies that the graph Kn can be viewed as the join of a circulant graph of order n - 1 with K1, that is, Kn = H(n;A) where $ A=\{1, 2, \ldots, (n-1)/2\}$.

Lemma 4.2    Let m and n be positive odd integers satisfying $3 \le m \le n < 3m$. If $A=\{a_1,a_2,\ldots,a_{(m-3)/2}<\frac{n-1}{2}\}$, with $a_1 < a_2 < \ldots < a_{(m-3)/2}$, then $C_m\;\vert\;H(n;A)$.

PROOF.Label the vertices of the subcirculant with $u_0,u_1, \ldots,u_{n-2}$. We have $u_iu_j\in
E(H(n;A))$ if and only if $j-i \in A\;\cup\;-A$. Let $\rho$ denote the permutation $(u_0\;u_1\;\cdots\;u_{n-2})(u)$. If L is any subgraph of H(n;A), then $\rho(L)$ is defined as $\rho\in\mathrm{Aut}(H(n;A))$.

Let P be the trail of length $\frac{m-3}{2}$ given by

\begin{displaymath}P=u_0,u_{a_1},u_{a_1-a_2},u_{a_1-a_2+a_3},\ldots, u_{a_1-a_2+a_3-a_4
+\cdots \mp a_{(m-5)/2}\pm a_{(m-3)/2}}.\end{displaymath}

Note that P uses precisely one edge of each length in A. Also note that alternate vertices starting with ua1 have strictly increasing subscripts, while alternate vertices starting with u0 have strictly decreasing subscripts. Thus, the vertices of P are distinct so that Pis a path. The last edge used to form P has length $a_{(m-3)/2}<
\frac{n-1}{2}$ so that all the vertices of P lie in the interval containing u0 from $u_{a_1-a_2+a_3-a_4+\cdots \pm
a_{(m-3)/2}}$ to $u_{a_1-a_2+\cdots \mp a_{(m-5)/2}}$. This interval has length at most (n-3)/2. Therefore, the path $\rho^{(n-1)/2}(P)$ is vertex-disjoint from P, and the edge of length ai in P is diametrically opposed to the edge of length ai in $\rho^{(n-1)/2}(P)$.

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

\begin{displaymath}w = u_{a_1-a_2+a_3-a_4+
\cdots\mp a_{(m-6)/2}\pm a_{(m-3)/2}}.\end{displaymath}

Form a cycle C of length mby taking

\begin{eqnarray*}C &=& \{w\rho^{(n-1)/2}(w),uu_0,uu_{(n-1)/2},\}\cup P\cup\rho^{(n-1)/2}(P).

Then $C,\rho(C),\rho^2(C),\ldots,\rho^{(n-3)/2}(C)$ is a partition of the edge set of H(n;A) into m-cycles.

We now present the proof of our second main result.

PROOF OF THEOREM 1.2. Let m and n be positive odd integers with $n(n-1)\equiv 0({\rm mod}\ 2m)$. Recall that by a result given in [7], it is sufficient to prove the theorem for values of m and n with $m \le n < 3m$. Thus, we may write n as n = m+r or n = 2m+rwhere $0\le r<m$. Let $ A=\{1, 2, \ldots, (n-1)/2\}$ and label the vertices of the graph H(n;A) with $u_0,u_1, \ldots, u_{n-2}, u$, where u is the vertex of K1 (see Definition 4.1). Let $\rho$ denote the permutation $(u_0\;u_1\;\cdots\;u_{n-1})(u)$. There are two cases depending on whether n = m + r or n = 2m+r.

CASE 1. SUPPOSE THAT N = M+R. Clearly, if r=0, we are done by the Walecki Hamilton decomposition of Kn 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 $X(n-1;B \cup -B)$into m-cycles. Since $H(n;A) = H(n; A-B) \oplus X(n-1;B \cup -B)$ 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 = 2ea, with a odd. Since $n(n-1)\equiv 0({\rm mod}\ 2m)$, we also have that $r(r-1)\equiv 0({\rm mod}\ 2m)$. Since r(r-1)/2= 2e-1a(2ea-1), we may write m as m = a'b' where $a'\;\vert\;a$ and $b'\;\vert\;(2^ea-1)$. Let r/2 = a'c. Next,

n-1=m+r-1 = a'b'+2ea-1=b'(a'+(2ea-1)/b').

We partition the vertices of $H=X(n-1;B\cup -B)$ into b' segments with $\ell = a'+
(2^ea-1)/b'$ vertices in each segment. Observe that $\ell$ is even. We now proceed depending on the congruence class of a' modulo 4.

SUBCASE 1.1. SUPPOSE THAT #MATH285#. Define the path P0,0 of length a'-1 as follows when a'>7:

\begin{eqnarray*}P_{0,0} & = & u_{0},u_2,u_{-1},u_{3},\ldots,u_{-(a'-7)/4},u_{(a...
...& u_{(a'+5)/4}, \ldots, u_{-(a'-1)/2}, u_{(a'+1)/2}, u_{1-\ell}.

Observe that the lengths of the edges of P0,0 are $2, 3, \ldots,
(a'-3)/2, (a'-1)/2+\ell, (a'+1)/2,\ldots, a'$. Obtain the path P0,1 as before, that is, $P_{0,1}=\rho^\ell(P_{0,0})$. Since $\ell - (a'-1)/2 \ge (a'+3)/2$, the paths P0,0 and P0,1 are vertex-disjoint. Again, let the powers of $\rho^\ell$ act on P0,0 to obtain the paths P0,0, P0,1, $\ldots$, P0, b'-1. Let $B_0 = \{2, 3, \ldots, (a'-3)/2, (a'-1)/2+\ell,
(a'+1)/2, \ldots, a'\}$.

When a'=3, let $P_{0,0}=u_0,u_2,u_{1-\ell}$, and when a'=7, let $P_{0,0}=u_0,u_2,u_{-2},u_3,u_{-3},u_4,u_{1-\ell}$.

If c > 1, then, for each $j = 1, 2, \ldots, c-1$, obtain the path Pj,0 from P0,0 by adding $j\ell$ to the subscripts of the even vertices of P0,0, that is,

\begin{eqnarray*}P_{j,0} & = & u_{0},u_{2+j\ell},u_{-1},u_{3+j\ell},\ldots,u_{-(...

and continue as before letting the powers of $\rho^\ell$ act on Pj,0. Then the lengths of the edges of the paths are $B_j = \{2+j\ell,\ldots,
(a'-3)/2+j\ell, (a'-1)/2+(j+1)\ell, (a'+1)/2, \ldots, a'+j\ell\}$.

For $0 \le j \le c-1$, let ${\cal P}_j$ denote the collection of paths Pj,0, Pj,1, $\ldots$, Pj,b'-1. Then the set $B_0 \cup B_1
\cup \cdots \cup B_{c-1}$ consists of c(a'-1) lengths. Also, the longest edge of $B_0 \cup B_1
\cup \cdots \cup B_{c-1}$ has length $(a'-1)/2 + c\ell$, and it is easy to see that $(a'-1)/2+c\ell <
(n-1)/2$. Note also that $B_0 \cup B_1
\cup \cdots \cup B_{c-1}$contains no length that is congruent to $\pm 1$ modulo $\ell$ as long as $a'<\ell-1$ (we handle this case separately). Thus, we may use circulants of order b' to link each family ${\cal P}_j$ into an m-cycle Cj as in Subcase 2.2 of the proof of Theorem 1.1. Then the collection

\begin{displaymath}\{C_j, \rho(C_j), \rho^2(C_j), \ldots, \rho^{\ell-1}(C_j)\; \;\vert\; \;
0 \le j \le c-1\}\end{displaymath}

is a partition of the edge set of the circulant H into m-cycles.

If $\ell=a'+1$ and a'>3, let

\begin{eqnarray*}P_{0,0} & = & u_0,u_{a'},u_1,u_{a'-1},\ldots,u_{(a'-3)/4},u_{a'...

For a'=3, let P0,0=u0,u3,u2. The lengths used are $1,2,\ldots,
(a'-1)/2,(a'+3)/2,(a'+5)/2,\ldots,a'$. Let the other paths in ${\cal P}_0,
{\cal P}_1,\ldots,{\cal P}_{c-1}$ be obtained exactly as above. We use circulants of order b' for linking the families of paths into m-cycles. The difference now is that the linking edges have lengths congruent to $(a'+1)/2=\ell/2$ modulo $\ell$. We must be careful because -(a'+1)/2is congruent to (a'+1)/2 modulo $\ell$.

In this case, b'=r-1 and if we express b' in the form b'=a't+s, $0\leq s<a'$, we find that a'b'=m divides the number of edges in Km+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 vi to vk, then we would be joining the terminal vertex of some Pj,i to the initial vertex of Pj,k. The length of such a linking edges is $(k-i-1)\ell+(a'+1)/2$. If the arc goes from vk to vi, then the length of the linking edge is $(k-i)\ell+
(a'+1)/2$. So if c=4q, then we use Hamilton decompositions of the degree 4 circulants $X(b';\{\pm 1,\pm 3\}),X(b';\{\pm 5,\pm 7\}),
\ldots,X(b';\{\pm(2q-3),\pm(2q-1)\})$ as before. Since $b'=8qa'+1\geq
24q+1$, the lengths of the linking edges are smaller than (n-1)/2. Similar arguments work for c=4q+1, c=4q+2 and c=4q+3.

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

\begin{eqnarray*}P_{0,0} & = & u_0,u_1,u_{-1},u_2,u_{-2},\ldots,u_{(a'-1)/2},u_{-(a'-1)/2}.

Obtain the paths $P_{0,1}, P_{0,2}, \ldots, P_{0,b'-1}$. by letting powers of $\rho^\ell$ act on P0,0 in the usual way. For each j satisfying j>0, obtain Pj,0 by adding $j\ell$ to the subscripts of all the even vertices of P0,0. Then obtain $P_{j,1},
\ldots,P_{j,b'-1}$ from Pj,0 by letting powers of $\rho^\ell$ act on it. Let ${\cal P}_j$ denote the family of paths $P_{j,0}, P_{j,1},
\ldots, P_{j,b'-1}$.

If c = 4q, then $b'\geq 39q$. Use the sets of paths ${\cal P}_0,
{\cal P}_1,\ldots,{\cal P}_{4q-1}$. Note that the longest edge has length $a'-1+(4q-1)\ell$. We use Hamilton directed cycles arising from Hamilton decompositions of $X(b';\{\pm 6q,\pm(6q+1)\})$, $X(b';\{\pm(6q+2),\pm(6q+3)\})$,..., $X(b';\{\pm(8q-2),\pm(8q-1)\})$. These linking edges have length longer than $a'-1+(4q-1)\ell$ 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=4q+1, use the sets of paths ${\cal P}_2,{\cal P}_3,
\ldots,{\cal P}_{4q+2}$, the same linking scheme for 4q of the families, and edges of length (a'+3)/2 to link together the other family. The cases c=4q+2 and c=4q+3 can be done similarly.

Finally, suppose that $\ell \ge a'+3$. Let $t = \ell - (a'+1)/2 - 2$and note that t is odd. Consider the walk P0,0 of length a'-1defined by

\begin{eqnarray*}P_{0,0} & = & u_{-t},u_0,u_2,u_{-1},\ldots,u_{-(t-3)/2},u_{(t+1...

Since t > (a'+2) - (a'+1)/2 - 2 = (a'-1)/2, we have that P0,0 is a path. When t=3 and a'=5, the preceding path is P0,0=u-3, u0,u2,u-2,u4. Continue as in Case 1, letting the powers of $\rho^\ell$ act on P0,0 to obtain the paths $P_{0,1}, P_{0,2}, \ldots, P_{0,b'-1}$. Observe that $\ell - t = (a'+5)/2$ so that these paths are vertex-disjoint. Join the last vertex of P0,i to the first vertex of P0,i+1 for $0 \le i \le b'-2$, and join the last vertex of P0,b'-1 to the first vertex of P0,0 to form the m-cycle C0. The lengths of the edges of C0 are the elements of the set $B_0 = \{1, 2, \ldots, t, t+1, t+3, \ldots, a', a'+1\}$.

If c > 1, then, for each $j = 1, 2, \ldots, c-1$, obtain the path Pj,0 from P0,0 by subtracting $j\ell$ from the subscript of the first vertex and adding $j\ell$ to the subscripts of the remaining odd vertices of P0,0, that is,

\begin{eqnarray*}P_{j,0} & = & u_{-(j\ell+t)}, u_0, u_{2+j\ell}, u_{-1}, \ldots,...

and continue as before letting the powers of $\rho^\ell$ act on Pj,0. Join the last vertex of Pj,i to the first vertex of Pj,i+1 for $0 \le i \le b'-2$ and join the last vertex of Pj,b'-1 to the first vertex of Pj,0 to form the m-cycle Cj. Note that these edges all have length $2j\ell-1$. Thus the lengths of the edges of Cj are the elements of the set $B_j = \{2+j\ell,3+j\ell,\ldots,t+1+j\ell,t+3 +
j\ell, \ldots, a'+j\ell, a'+1+j\ell, 2j\ell -1\}$.

Let $B= B_0 \cup B_1 \cup \cdots \cup B_{c-1}$. Then the longest edge of B has length $2(c-1)\ell - 1$ or $a'+1 + (c-1)\ell$. We already have seen that $2(c-1)\ell - 1 < n-1$ and it is not hard also to see that $a'+1+(c-1)\ell < (n-1)/2$. Thus B consists of r/2 distinct lengths. Therefore, the collection

\begin{displaymath}\{C_j, \rho(C_j), \rho^2(C_j), \ldots, \rho^{\ell-1}(C_j)\;\vert\;
0 \le j \le c-1\}\end{displaymath}

is a partition of the edge set of the circulant $H=X(n-1;B\cup -B)$into m-cycles.

CASE 2. SUPPOSE THAT #MATH356#N = 2M + R. In this case, ris odd and suppose first that r=1 so that n = 2m + 1. Relabel the vertex u of H(n;A) with un-1, and as before, for $0 \le i, j
\le n-1$, the length of the edge uiuj is either i - j or j - i, depending on which lies between 1 and (n-1)/2 modulo n. Let $\tau
= (u_0\;u_1\;\cdots\;u_{n-1})$. Next, suppose that (m-1)/2 is odd. Consider the m-cycle C given by

\begin{eqnarray*}C &=& u_0, u_1, u_{-1}, u_2, u_{-2}, \ldots, u_{(m-3)/4}, u_{-(...

Then $C, \tau(C), \tau^2(C), \ldots, \tau^{n-1}(C)$ is a partition of the edge set of Kn into m-cycles. Now suppose that (m-1)/2 is even. Consider the m-cycle C given by

\begin{eqnarray*}C &=& u_0, u_1, u_{-1}, u_2, u_{-2}, \ldots, u_{(m-1)/4}, u_{-(...
...m+11)/4}, \ldots, u_{-(m-3)/2)}, u_{(m+1)/2},
u_{-(m+1)/2}, u_0.

As before, $C, \tau(C), \tau^2(C), \ldots, \tau^{n-1}(C)$ is a partition of the edge set of Kn into m-cycles. Therefore, the graph K2m+1can be decomposed into m-cycles.

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 nvertices into segments, and we use the remaining m lengths to form a single m-cycle which is acted on by $\tau$.

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


giving us a lower bound on the number of segments.

Write c in the form $c=4k+t, 0\leq t\leq 3$. Suppose t=0 and (a'-1)/2 is odd. Let

\begin{eqnarray*}P_{0,0} & = & u_0,u_1,u_{-1},u_2,u_{-2},\ldots,u_{(a'-3)/4},u_{...
...& u_{-(a'+1)/4},\ldots,u_{-(a'-3)/2},u_{(a'+1)/2},u_{-(a'-1)/2}.

The lengths of the edges of P0,0 are $1,2,\dots,(a'-3)/2,(a'+1)/2,
\ldots,a'$. Obtain $P_{0,1}, P_{0,2}, \ldots, P_{0,b'-1}$ in the usual way by letting powers of $\tau^\ell$ act on P0,0.

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

In the special case that a'=3, we use P0,0=u0,u2,u-1 and P1,0=u0,u4,u-1.

Let P2j,0 be obtained by adding $j\ell$ to the subscripts of the even vertices of P0,0, and obtain $P_{2j,1},\dots,P_{2j,b'-1}$ from P2j,0 in the usual way. Finally, obtain P2j+1,0 by adding $j\ell$to the subscripts of the even vertices of P1,0, and obtain $P_{2j+1,1},\ldots,P_{2j+1,b'-1}$ as before. Let ${\cal P}_j=\{P_{j,0},
\ldots,P_{j,b'-1}\}$. None of the paths use edges whose lengths are congruent to $\pm(a'-1)/2$ modulo $\ell$. We use edges of these lengths to link the paths of ${\cal P}_j$ 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 $X(b';\{\pm(2s-1),\pm 2s\})$ for the collection of paths ${\cal P}_{4s-4},{\cal P}_{4s-3},{\cal P}_{4s-2}$ and ${\cal P}_{4s-1}$, $1\leq s\leq k$.

Let us verify that all the lengths employed are distinct. The length of the longest edge is $2k\ell+(a'-1)/2$, and the number of vertices is $n=b'\ell>2c\ell=8k\ell$. 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 $\ell_1,
\ell_2,\ldots,\ell_m$. Since the longest length already used is $2k\ell+(a'-1)/2$ and (r-1)/2 lengths have been used, the lengths $\ell_{s+1},\ldots,\ell_m$ consist of successive integers from $2k\ell+(a'+1)/2$ through (n-1)/2, where $s=2k\ell+(a'-1)/2-(r-1)/2$. Start a path P according to


noting that s is odd. All lengths $\ell_1,\ell_2,\ldots,\ell_{s+1}$are used in P. Let $-x=\ell_1-\ell_2+\cdots+\ell_s-\ell_{s+1}$ so that the terminal vertex of P is distance x from u0. We know that $\ell_{s+1}=2k\ell+(a'+1)/2$ is even and that the remaining lengths are successive integers. We shall complete P to a path P'of length m-2 by continuing in the form

\begin{eqnarray*}& & u_{\ell_1-\ell_2+\cdots+\ell_s-\ell_{s+1}+\ell_{s+2}},

and so on until reaching $u_{\ell_1-\ell_2+\cdots+\ell_j-\ell_{j+1}+
\ell_{j+3}-\ell_{j+4}+\cdots+\ell_{m-1}}=u_y$. Notice that P' has been obtained by successively zigzagging with edges of increasing length and omitting one edge of odd length $\ell_{j+2}$. Let u-z be the vertex immediately preceding uy in P'. If we wish to add an edge of length (n-1)/2 to P', it will go from uy to either u-z-1or u-z-2. Let w be the odd integer amongst z+1 and z+2. If $w\geq 2k\ell+(a'+1)/2$, then let w be the odd length $\ell_{j+2}$omitted to form P'. Adding the 2-path uy,u-w,u0 to P' yields an m-cycle C' using all of the missing lengths precisely once. Letting $\tau$ act on C' completes the decomposition.

This leaves us with the problem of what to do when $w<2k\ell+(a'+1)/2$. The first step is to let $\ell_{s+2}=2k\ell+(a'+3)/2$ be the odd length edge we delete in forming P'. Currently, P' ends with uy-1,u-z,uy, the edge uy-1u-zhas length (n-5)/2, and the edge u-zuy has length (n-3)/2. Perform the following alteration of P'. From uy-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 $2k\ell+(a'+3)/2$, then we close the path to an m-cycle with an edge of length $2k\ell+(a'+3)/2$. If $z+4<2k\ell+(a'+3)/2$, then start the alteration of P' at uy-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 $2k\ell+(a'+3)/2$, 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 $u_{-2k\ell
-(a'+3)/2}$. We have

\begin{eqnarray*}\frac{n-1}{2}-(2k\ell+\frac{a'-+3}{2}) & > & \frac{8k\ell-1}{2}-2k\ell-
\frac{a'+3}{2}\\ & = & 2k\ell-2-\frac{a'}{2}

edges whose lengths are consecutive integers from $2k\ell+(a'+5)/2$through (n-1)/2. We wish to show the longest subpath which would need to be reversed so that P' terminates at $u_{-2k\ell
-(a'+3)/2}$ has length less than $2k\ell-(a'/2)$

Notice that $2a'<
\ell-(a'-1)/2$ implies $\ell,\ell+a'+(a'-1)/2,
\ell+2a'+1$ are successive integers in the sequence $\ell_1,
\ell_2,\ldots,\ell_m$. 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 $\ell-(a'-1)/2\leq 2a'$, we have $\ell_1=
a'+(a'-1)/2$ and $\ell_2=2a'+1$. 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

\begin{displaymath}w\geq \frac{m-1}{2}+\frac{a'+3}{2} > \frac{4k\ell}{3}-\frac{1}{2}

using the facts m>n/3 and $n>8k\ell$. Since


the longest subpath which would need to be reversed has length less than $\frac{4k\ell}{3}+1$. Observe that

\begin{eqnarray*}2k\ell-2-\frac{a'}{2}-(\frac{4k\ell}{3}+1) & = & \frac{2k\ell}{...
... \geq & \frac{5\cdot 3}{6}+\frac{2}{3}-3\\ & = & \frac{1}{6} > 0

because $a'\geq 3$, $k\geq 1$ and b'|r. (When k=0 the previous case applies.) So there is a sufficiently long sequence of consecutive edge lengths available for reversing a subpath to allow us to form an m-cycle.

If c=4k+1, we link the paths of ${\cal P}_0$ to form an m-cycle using edges of length $\ell+(a'-1)/2$. We then use Hamilton decompositions of

\begin{displaymath}X(b';\{\pm 2,\pm 3\}),\ldots,X(b';\{\pm(2k+1),
\pm 2k\})\end{displaymath}

to handle the families ${\cal P}_1,\ldots,{\cal P}_{4k}$. The remaining m lengths are handled as in the previous case.

For c=4k+2, we link the paths of ${\cal P}_0$ and ${\cal P}_1$to form two m-cycles using edges of lengths $\ell\pm(a'-1)/2$, respectively. The remaining families of paths and the resulting mlengths are done as before. Finally, for c=4k+3, use the lengths $\ell\pm(a'-1)/2$ and $2\ell+(a'-1)/2$ to link the paths ${\cal P}_0$, ${\cal P}_1$ and ${\cal P}_2$, respectively. Use Hamilton decompositions of

\begin{displaymath}X(b';\{\pm 3,\pm 4\}),\ldots,X(b';\{\pm 2k,\pm(2k+1)\})\end{displaymath}

for ${\cal P}_3,\ldots,{\cal P}_{4k+2}$. The remaining m-lengths are done as before.

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

\begin{eqnarray*}P_{0,0} & = & u_0,u_1,u_{-1},u_2,u_{-2},\ldots,u_{(a'-1)/4},
... u_{-(a'+3)/4},\ldots,u_{-(a'-3)/2},

The path P0,0 uses edges of lengths $1,2,\ldots,(a'_1)/2,(a'+3)/2,
\ldots,a'-1,a'+1$. One slight difference here is that the length a'has not been used. Thus, we start the path P1,0 as u0,ua', u-2 and note that the lengths of the first two edges are a' and a'+2 neither of which appear amongst the lengths for P0,0. We then continue the zigzag pattern as in P0,0 except that no more vertices are omitted from the interval not containing u0 from u-2 to u-(a'+1)/2. This means that the path P1,0 also terminates at u(-a'+1)/2. This means that the lengths of the connecting edges used to link families of paths together to form m-cycles are congruent to $\pm(a'+1)/2$ modulo $\ell$. Hence, we want to make certain we do not use an edge with length $\ell-(a'+1)/2$in P1,0. Since $\ell-(a'+1)/2$ is even, we can avoid using it by shifting the vertices in the interval containing ua'+1 from ua' to ua'+(a'-3)/2 if $\ell-(a'+1)/2<2a'-1$. Otherwise, we need shift no vertices in that interval. With these two starting paths the argument is the same as the preceding case. This completes the proof of Theorem 1.2.

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

Brian &