The Odd Case

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 $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 K_n.

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 K₁ is labeled u.

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₁, that is, K_n = 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

$$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}}.$$

Note that P uses precisely one edge of each length in A. Also note that alternate vertices starting with u_a1 have strictly increasing subscripts, while alternate vertices starting with u₀ 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 u₀ 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 a_i in P is diametrically opposed to the edge of length a_i in $\rho^{(n-1)/2}(P)$.

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

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

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). \end{eqnarray*}$$

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 K₁ (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 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 $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 = 2^ea, 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= 2^e-1a(2^ea-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'+2^ea-1=b'(a'+(2^ea-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 P_0,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}. \end{eqnarray*}$$

Observe that the lengths of the edges of P_0,0 are $2, 3, \ldots, (a'-3)/2, (a'-1)/2+\ell, (a'+1)/2,\ldots, a'$. Obtain the path P_0,1 as before, that is, $P_{0,1}=\rho^\ell(P_{0,0})$. Since $\ell - (a'-1)/2 \ge (a'+3)/2$, the paths P_0,0 and P_0,1 are vertex-disjoint. Again, let the powers of $\rho^\ell$ act on P_0,0 to obtain the paths P_0,0, P_0,1, $\ldots$, P_{0, 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 P_j,0 from P_0,0 by adding $j\ell$ to the subscripts of the even vertices of P_0,0, that is,

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

and continue as before letting the powers of $\rho^\ell$ act on P_j,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 P_j,0, P_j,1, $\ldots$, P_j,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 C_j as in Subcase 2.2 of the proof of Theorem 1.1. Then the collection

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

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'... ...,u_{a'-(a'+1)/4},\ldots,u_{(a'-1)/2},u_{(a'+3)/2}, u_{(a'+1)/2}. \end{eqnarray*}$$

For a'=3, let P_0,0=u₀,u₃,u₂. 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 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 $(k-i-1)\ell+(a'+1)/2$. If the arc goes from v_k to v_i, 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}. \end{eqnarray*}$$

Obtain the paths $P_{0,1}, P_{0,2}, \ldots, P_{0,b'-1}$. by letting powers of $\rho^\ell$ act on P_0,0 in the usual way. For each j satisfying j>0, obtain P_j,0 by adding $j\ell$ to the subscripts of all the even vertices of P_0,0. Then obtain $P_{j,1}, \ldots,P_{j,b'-1}$ from P_j,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 P_0,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... ...)/2},u_{-(t+3)/2},u_{(t+7)/2},\ldots,u_{-(a'-1)/2},u_{(a'+3)/2}. \end{eqnarray*}$$

Since t > (a'+2) - (a'+1)/2 - 2 = (a'-1)/2, we have that P_0,0 is a path. When t=3 and a'=5, the preceding path is P_0,0=u_-3, u₀,u₂,u_-2,u₄. Continue as in Case 1, letting the powers of $\rho^\ell$ act on P_0,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 P_0,i to the first vertex of P_0,i+1 for $0 \le i \le b'-2$, and join the last vertex of P_0,b'-1 to the first vertex of P_0,0 to form the m-cycle C₀. The lengths of the edges of C₀ 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 P_j,0 from P_0,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 P_0,0, that is,

$$\begin{eqnarray*}P_{j,0} & = & u_{-(j\ell+t)}, u_0, u_{2+j\ell}, u_{-1}, \ldots,... ...)/2},u_{(t+7)/2+j\ell},\ldots,u_{-(a'-1)/2}, u_{(a'+3)/2+j\ell}. \end{eqnarray*}$$

and continue as before letting the powers of $\rho^\ell$ act on P_j,0. Join the last vertex of P_j,i to the first vertex of P_j,i+1 for $0 \le i \le b'-2$ and join the last vertex of P_j,b'-1 to the first vertex of P_j,0 to form the m-cycle C_j. Note that these edges all have length $2j\ell-1$. Thus the lengths of the edges of C_j 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

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

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 u_n-1, and as before, for $0 \le i, j \le n-1$, the length of the edge u_iu_j 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_{-(... ...4},u_{(m+9)/4},u_{-(m+5)/4},\ldots,u_{(m+1)/2},u_{-(m-1)/2},u_0. \end{eqnarray*}$$

Then $C, \tau(C), \tau^2(C), \ldots, \tau^{n-1}(C)$ is a partition of the edge set of K_n 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. \end{eqnarray*}$$

As before, $C, \tau(C), \tau^2(C), \ldots, \tau^{n-1}(C)$ is a partition of the edge set of K_n into m-cycles. Therefore, the graph K_2m+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=2^ea+1, a'|a, b'|(2^ea+1), m=a'b' and m>r. Then n=2m+r=b'(2a'+(2^ea+1)/b'). Chop the vertices into b' segments each having 2a'+(2^ea+1)/b' vertices. Let c=(r-1)/2a'=2^e-1a/a'. We have

$$b'=\frac{m}{a'}>\frac{r}{a'}>\frac{2^ea}{a'}=2c$$

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}. \end{eqnarray*}$$

The lengths of the edges of P_0,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 P_0,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 P_1,0we do not want to use an edge of length $\ell-(a'-1)/2$. 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 Pare $a'+1,a'+2,\ldots,a'+(a'-3)/2,a'+(a'+1)/2,\ldots,2a'$. If $2a'< \ell-(a'-1)/2$, then let P_1,0=P. If $\ell-(a'-1)/2\leq 2a'$, 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 $\ell-(a'-1)/2$ being omitted. Since $\ell-(a'-1)/2$ is even, the omitted vertex is in the interval from u₀ to $u_\ell$ and the last vertex in the interval from u₀ to $u_\ell$ in the resulting path still is u_a'+(a'+1)/2. This is the path P_1,0. Now obtain $P_{1,1}, P_{1,2}, \ldots, P_{1,b'-1}$ from P_1,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 P_0,0=u₀,u₂,u_-1 and P_1,0=u₀,u₄,u_-1.

Let P_2j,0 be obtained by adding $j\ell$ to the subscripts of the even vertices of P_0,0, and obtain $P_{2j,1},\dots,P_{2j,b'-1}$ from P_2j,0 in the usual way. Finally, obtain P_2j+1,0 by adding $j\ell$to the subscripts of the even vertices of P_1,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

$$P=u_0,u_{\ell_1},u_{\ell_1-\ell_2},u_{\ell_1-\ell_2+\ell_3},\ldots, u_{\ell_1-\ell_2+\ell_3-\cdots+\ell_s-\ell_{s+1}}$$

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 u₀. 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}}, u_{\... ..._{\ell_1-\ell_2+\cdots+\ell_j-\ell_{j+1}+\ell_{j+3}-\ell_{j+4}}, \end{eqnarray*}$$

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 u_y in P'. If we wish to add an edge of length (n-1)/2 to P', it will go from u_y 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 u_y,u_-w,u₀ 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 u_y-1,u_-z,u_y, the edge u_y-1u_-zhas length (n-5)/2, and the edge u_-zu_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 $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 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 $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} \end{eqnarray*}$$

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

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

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

$$2k\ell+\frac{a'+3}{2}-w<2k\ell+\frac{a'+3}{2}-(\frac{4}{3}k\ell- \frac{1}{2}+\frac{a'+3}{2})=\frac{2k\ell}{3}+\frac{1}{2},$$

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 \end{eqnarray*}$$

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

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

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

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

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_... ... u_{-(a'+3)/4},\ldots,u_{-(a'-3)/2}, u_{(a'+1)/2},u_{-(a'+1)/2}. \end{eqnarray*}$$

The path P_0,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 P_1,0 as u₀,u_a', 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 P_0,0. We then continue the zigzag pattern as in P_0,0 except that no more vertices are omitted from the interval not containing u₀ from u_-2 to u_-(a'+1)/2. This means that the path P_1,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 P_1,0. Since $\ell-(a'+1)/2$ is even, we can avoid using it by shifting the vertices in the interval containing u_a'+1 from u_a' to u_a'+(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.

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.