The Even Case

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 $n(n-2)\equiv 0({\rm mod}\ 2m)$. 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.

Definition 3.1   If A is a set of positive integers, then $-A= \{-a:a\in A\}$.

Definition 3.2   Let $A\subseteq\{1,2,\ldots,n/2-1\}$, where n is a positive even integer. Let G be the circulant graph of order n-2with connection set $A \cup -A$, and u and w be two independent vertices, neither of which are vertices of G. Define $H(n;A)=G\bowtie \{u,w\}$, that is, $H(n;A)=G\bowtie \overline{K_2}$, where the vertices of $\overline{K_2}$ are labeled uand w.

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 $\overline{K_2}$, that is, K_n - I = H(n;A), where $A=\{1, 2, \ldots, (n-4)/2\}$. Thus the edges of length (n-2)/2in the circulant together with the edge uw make up the edges of the 1-factor I.

Definition 3.3   Let u_iu_j be an edge of length j-i in a circulant graph of order n. The edge of length j-i diametrically opposed to u_iu_jis the edge joining u_i+n/2 and u_j+n/2.

Lemma 3.4    Let m and n be positive even integers satisfying $m \ge 4$, n < 2m, and $m \equiv 0 ({\rm mod}\ 4)$. If $A=\{a_1,a_2,\ldots,a_{(m-4)/2}\}$, where $a_1,a_2,\ldots,a_{(m-4)/2}$are positive integers satisfying $a_1 < a_2 < \ldots < a_{(m-4)/2}$, then $C_m\;\vert\;H(n;A)$.

PROOF.Label the vertices of the subcirculant with $u_0,u_1, \ldots,u_{n-3}$. We have $u_iu_j\in E(H(n;A))$ if and only if $j-i \in A$. Let $\rho$ denote the permutation $(u_0\;u_1\;\cdots\;u_{n-3})(u)(w)$. 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-4}{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+a_{(m-6)/2}-a_{(m-4)/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 alternating vertices starting with u₀have strictly decreasing subscripts. Thus, the vertices of P are distinct so that P is a path. The last edge used to form P has length $a_{(m-4)/2}<\frac{n-2}{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-a_{(m-4)/2}}$to $u_{a_1-a_2+\cdots+a_{(m-6)/2}}$. This interval has length at most (n-4)/2. Therefore, the path $\rho^{(n-2)/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-2)/2}(P)$

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

$$\begin{eqnarray*}C & = &\{uu_0,uu_{(n-2)/2}, wu_{a_1-a_2+\cdots-a_{(m-4)/2}}, wu... ...2+\cdots -a_{(m-4)/2}}\} \cup \\ && P\;\cup\;\rho^{(n-2)/2}(P). \end{eqnarray*}$$

From the above remarks, it follows that $C,\rho(C),\rho^2(C),\ldots, \rho^{(n-4)/2}(C)$ is a partition of the edge set of H(n;A) into m-cycles.

We now present the proof of the first main theorem.

PROOF OF THEOREM 1.1. Let m and n be positive even integers with $n(n-2)\equiv 0({\rm mod}\ 2m)$. 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 $K_{n/2}\wr \overline{K_2}$, that is, replace every vertex of K_n/2 by a copy of $\overline{K_2}$ 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 $P\wr \overline{K_2}$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 < 2m, say n=m+r for some positive integer r with $0\le r<m$. 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 $n(n-2)\equiv 0({\rm mod}\ 2m)$ implies that $r(r-2)\equiv 0({\rm mod}\ 2m)$, 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 $A=\{1, 2, \ldots, (n-4)/2\}$ and label the vertices of the graph H(n;A) with $u_0,u_1,\ldots,u_{n-3},u,w$, where u and w are the two vertices of $\overline{K_2}$ (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 $\;\vert\;B\;\vert\;=r/2$, and that we can decompose the circulant $X(n-2; B\cup-B)$ into m-cycles. Then since $H(n;A) = H(n;A-B) \oplus X(n-2; B\cup-B)$ 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 $H=X(n-2;B\cup-B)$ 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 #MATH97#. Let r = 2^ea where a is odd and $e \ge 3$. Thus r(r-2)/2=2^ea(2^e-1a-1). Since m divides r(r-2)/2 evenly, we have that m=2^da'b', where $a'\;\vert\;a$, $b'\;\vert\;(2^{e-1}a-1)$, and $2 \le d < e$. Then

n-2=m+r-2=2^da'b'+2^ea-2=b'(2^da'+(2^ea-2)/b').

Partition the vertices of the circulant H into b' segments, each with $\ell = 2^da'+(2^ea-2)/b'$ vertices. Each segment will contribute 2^da' edges to an m-cycle. Define the path P_0,0 by

$$\begin{eqnarray*}P_{0,0}&=&u_0, u_2, u_{-1}, u_3, u_{-2}, \ldots, u_{2^{d-2}a'},... ...1},\ldots,u_{2^{d-1}a'+1}, u_{-2^{d-1}a'+1}, u_{\ell+1}, u_\ell. \end{eqnarray*}$$

Let $P_{0,1}=\rho^\ell(P_{0,0})$, where $\rho$ is the permutation from the proof of Lemma 3.4. Since $\ell > 2^da'$ implies that $2^{d-1}a'+1 < \ell - 2^{d-1}a'+1$, the vertices of P_0,1 are distinct from the vertices of P_0,0 except for $u_\ell$, which is the last vertex of P_0,0 and the first vertex of P_0,1. Similarly, the paths

$$P_{0,0}, P_{0,1}=\rho^\ell(P_{0,0}), P_{0,2}=\rho^{2\ell}(P_{0,0}), \ldots, P_{0,b'-1}=\rho^{(b'-1)\ell}(P_{0,0})$$

are vertex-disjoint except that the path P_0,i begins at the last vertex of P_0,i-1 for $1 \le i \le b'-1$ and P_0,b'-1 ends at u₀. Thus $C_0 = P_{0,0} \cup P_{0,1} \cup \cdots\cup P_{0, b'-1}$ is an m-cycle and the lengths of the edges of C₀ are $1, 2, \ldots, 2^{d-1}a'-1, 2^{d-1}a'+\ell,2^{d-1}a'+1, \ldots, 2^da'$.

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

$$P_{0,0}=u_0,u_3,u_{-1}, u_{\ell+1},u_{\ell}.$$

Let b=r/(2^d+1a') = 2^e-d-1a/a'. If b > 1, then obtain the path P_1,0 by adding $\ell$ to the subscripts of the even vertices of P_0,0, that is,

$$\begin{eqnarray*}P_{1,0}&=&u_0, u_{2+\ell}, u_{-1}, u_{3+\ell}, u_{-2}, \ldots, ... ..._{2^{d-1}a'+1+\ell}, \\ &&u_{-2^{d-1}a'+1}, u_{2\ell+1},u_\ell. \end{eqnarray*}$$

Next, obtain the paths $P_{1,1}, P_{1,2}, \ldots, P_{1,b'-1}$ by letting powers of $\rho^\ell$ act on P_1,0 in the same way they acted on P_0,0. Furthermore, the path P_1,i begins at the last vertex of P_{1, i-1} for $1 \le i \le b'-1$ and the last vertex of P_1,b'-1 is u₀. Thus, $C_1=P_{1,0} \cup P_{1,1 }\cup P_{1,2} \cup \cdots \cup P_{1, b'-1}$is an m-cycle, where the lengths of the edges of C₁ are $1+\ell, 2+\ell,3+\ell,\ldots,2^{d-1}a'-1+\ell,2^{d-1}a'+2\ell, 2^{d-1}a'+1+\ell, \ldots, 2^da'+\ell$.

Similarly, for each j with $2\le j\le b$, obtain the path P_j,0 by adding $j\ell$ to the subcripts of the even vertices of P_0,0. Then the paths $P_{j,1}, P_{j,2}, \ldots, P_{j,b'-1}$ are obtained by letting powers of $\rho^\ell$ act on P_j,0. Note here that P_j,i begins at the last vertex of P_j,i-1 for $1 \le i \le b'-1$ and the last vertex of P_j,b'-1 is u₀. Hence $C_j = P_{j,0}\cup P_{j,1}\cup \cdots \cup P_{j,b'-1}$ is an m-cycle and the lengths of the edges of C_j are $1+j\ell, 2+j\ell,3+j\ell,\ldots,2^{d-1}a'-1+j\ell, , 2^{d-1}a'+1+j\ell, \ldots, 2^da'+j\ell,2^{d-1}a'+(j+1)\ell$.

For $0 \le j \le b-1$, let B_j denote the set of lengths that C_juses, that is, $B_j = \{1+j\ell, 2+j\ell,3+j\ell,\ldots, 2^{d-1}a'-1+j\ell, 2^{d-1}a'+(j+1)\ell, 2^{d-1}a'+1+j\ell, \ldots, 2^da'+j\ell\}$. Let $B = B_0 \cup B_1 \cup \cdots \cup B_{b-1}$. Now the longest edge in B has length $b\ell+2^{d-1}a'$. Since 2^ea < 2^da'b' implies that $2^{e-d}a/a'+1 \le b'$, it follows that

$$\begin{eqnarray*}b\ell+2^{d-1}a'& = & 2^{e-d-1}\frac{a}{a'}\ell + 2^{d-1}a' = 2... ...2}\ell-\frac{2^{e-1}a-1}{b'}< \frac{b' \ell}{2} = \frac{n-2}{2}. \end{eqnarray*}$$

Therefore, the lengths of B are distinct and hence |B|=r/2. Thus, the collection

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

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

CASE 2. SUPPOSE THAT #MATH137#. Let r=8k+2 for some nonnegative integer k. In this case we have r(r-2)/2 = 8k(4k+1) = 2^ea(4k+1) where 2^ea=8k, a is odd, and gcd(a,4k+1)=1. Then m=2^da'b', where $2\leq d < e$, $a'\;\vert\;a$, and $b'\;\vert\;(4k+1)$. Let r/2=bb'. Then

n-2=2^da'b'+2^ea = 2^da'(b'+2^e-da/a').

Let $\ell = b'+2^{e-d}a/a'$ and note that $\ell \ge b'+2$. The proof now breaks into two subcases depending on the congruence class of b' modulo 4.

SUBCASE 2.1. SUPPOSE THAT #MATH145#. Observe that $b'\geq 5$ because b'=1 implies that $m=2^da'\leq 2^ea= r-2$ which is a contradiction. Let $s = \ell-(b'+1)/2 - 1$ and note that s is odd. Consider the walk P_0,0 defined by

$$\begin{eqnarray*}P_{0,0} & = & u_{-s}, u_0, u_2, u_{-1}, u_3, \ldots, u_{-(s-3)/... ... u_{-(s+3)/2}, u_{(s+5)/2}, \ldots, u_{-(b'-1)/2}, u_{(b'+1)/2}. \end{eqnarray*}$$

Since $s \ge (b'+2)-(b'+1)/2-1 = (b'-1)/2+1$, 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 $\ell-s=4$, and P_0,0=u_-3,u₀,u₂,u_-2,u₃. Observe that the lengths of the edges of P_0,0 are $2, 3, \ldots, b'$. Obtain the path P_0,1 as before, that is, $P_{0,1}=\rho^\ell(P_{0,0})$. Since $\ell - s = (b'+3)/2$, 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 $\rho^\ell$ act on P_0,0 to obtain the paths P_0,0, P_0,1, $\ldots$, P_{0, 2^da'-1}. Form the m-cycle C₀by joining the last vertex of P_0,i to the first vertex of P_0,i+1for $0 \le i \le 2^da'-2$ and joining the last vertex of P_0,2^da'-1to the first vertex of P_0,0. Necessarily, these edges all have length 1. Let $B_0 = \{1, 2,\ldots,b'\}$.

If b > 1, then obtain the path P_1,0 from P_0,0 by subtracting $\ell$ from the subscript of the first vertex and adding $\ell$ to the subscripts of the remaining odd vertices of P_0,0, that is,

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

Then the lengths of the edges of P_1,0 are $2+\ell, 3+\ell, \ldots, b'+\ell$. As before, let the powers of $\rho^\ell$ act on P_1,0 to obtain the paths $P_{1,0}, P_{1,1}, \ldots, P_{1, 2^da'-1}$. Form the m-cycle C₁ by joining the last vertex of P_1,i to the first vertex of P_1,i+1 for $0 \le i \le 2^da'-2$ and joining the last vertex of P_1,2^da'-1 to the first vertex of P_1,0. Note that these edges have length $2\ell-1$.

Similarly, for $2 \le j \le b-1$, obtain the path P_j,0 from P_0,0by 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. Again, letting the powers of $\rho^\ell$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 $0 \le i \le 2^da'-2$ and joining the last vertex of P_j,2^da'-1 to the first vertex of P_j,0. Observe that these edges have length $2j\ell-1$ and thus the cycle C_j has edges with lengths $2+j\ell, 3+j\ell, \ldots, b'+j\ell, 2j\ell-1$.

Let $B_j = \{2+j\ell, 3+j\ell, \ldots, b'+j\ell, 2j\ell-1\}$ for $1 \le j \le b-1$, and let $B=B_0 \cup B_1\cup \cdots \cup B_{b-1}.$Then the longest edge of B has length either $b'+(b-1)\ell$ or $2(b-1)\ell - 1$. Now r= 2bb' and m = 2^da'b', and since r < m, we have that 2b< 2^da'. Thus, $2b\ell < 2^da'\ell = n-2$. Therefore, the lengths $1, 2\ell-1, 4\ell-1, \ldots, 2(b-1)\ell - 1$ are all distinct. Next,

$$b'+(b-1)\ell < \ell + (2^{d-1}a'-1)\ell = 2^{d-1}a'\ell = (n-2)/2,$$

so that B consists of r/2 distinct lengths. Hence, the collection

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

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

SUBCASE 2.2. SUPPOSE THAT #MATH178#. Let P_0,0 be the path defined by

$$\begin{eqnarray*}P_{0,0}&=&u_0, u_2, u_{-1}, u_3, \ldots, u_{-(b'-7)/4}, u_{(b'+... ...&&u_{(b'+5)/4}, \ldots, u_{-(b'-1)/2}, u_{(b'+1)/2}, u_{1-\ell}. \end{eqnarray*}$$

Note that P_0,0 uses exactly one edge of each length $2, 3, \ldots, (b'-3)/2, (b'-1)/2+\ell,(b'+1)/2, \ldots, b'$ and uses no edge whose length is congruent to $\pm 1$ modulo $\ell$. Consider the paths

$$P_{0,1}=\rho^{\ell}(P_{0,0}),P_{0,2}=\rho^{2\ell}(P_{0,0}),\ldots, P_{0,2^da'-1}=\rho^{(2^da'-1)\ell}(P_{0,0}),$$

and note that P_0,i begins at vertex $u_{i\ell}$ and ends at $u_{(i-1)\ell+1}$.

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

$$P_{0,0}=u_0,u_2,u_{-2},u_3,u_{-3},u_4,u_{1-\ell}.$$

When b'=3, the condition m>r=2^ea+2 forces a'=a and d=e-1 which in turn implies $\ell=5$. The initial path P_0,0=u₀,u₃,u_-4 works in this case.

If b > 1, then obtain the path P_1,0 by adding $\ell$ to the subscripts of the even vertices of P_0,0, that is,

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

Next, obtain the paths $P_{1,1}, P_{1,2}, \ldots, P_{1,2^da'-1}$ by letting powers of $\rho^\ell$ act on P_1,0 as before. Observe that these paths use edges of lengths $2+\ell, 3+\ell, \ldots, (b'-3)/2+\ell, (b'-1)/2+2\ell, (b'+1)/2+\ell, \ldots, b'+\ell$.

Similarly, for each j with $2 \le j \le b-1$, obtain the path P_j,0by adding $j\ell$ to the subscripts of the even vertices of P_0,0. Then the paths $P_{j,1}, P_{j,2}, \ldots, P_{j,2^da'-1}$ are obtained by letting powers of $\rho^\ell$ act on P_j,0. For $0 \le j \le b-1$, let ${\cal P}_j$ denote the collection of paths $P_{j,0}, P_{j,1}, \ldots, P_{j,2^da'-1}$ and B_j denote the set of lengths that ${\cal P}_j$ uses, that is,

$$B_j = \{2+j\ell, 3+j\ell, \ldots,\frac{b'- 3}{2}+j\ell, \frac{b'-1}{2}+(j+1)\ell, \frac{b'+1}{2}+j\ell, \ldots, b'+ j\ell\}.$$

Observe that $B = B_0 \cup B_1 \cup \cdots \cup B_{b-1}$ has b(b'-1) lengths, and thus we must add b lengths to B to use r/2 lengths. The longest edge used thus far has length $(b'-1)/2+b\ell$ or $b'+(b-1)\ell$. Since r < m implies b < 2^d-1a', it follows that $b\ell < (n-2)/2$. Thus, the lengths $(b'-1)/2+\ell, (b'-1)/2 + 2\ell, \ldots, (b'-1)/2 + b\ell$ are distinct. Furthermore, since (n-2)/2 is an even multiple of $\ell$, we have that these lengths are all less than (n-2)/2 as well. In Subcase 2.1, we saw that $b'+(b-1)\ell < (n-2)/2$ regardless of the congruence class of b' modulo 4. Thus B consists of b(b'-1)distinct lengths.

Recall that $u_{i\ell}$ is the initial vertex of P_j,i and $u_{(i-1)\ell+1}$ is the terminal vertex of P_j,i for $0 \le j \le b-1$and $0\le i\le 2^da'-1$. Now we shall link the paths of ${\cal P}_j$ 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 $v_0,v_1, \ldots,v_{2^da'-1}$. Suppose we are given a Hamilton cycle C in G. Arbitrarily orient the cycle C to obtain a Hamilton directed cycle $\overrightarrow{C}$. If there is an arc from v_i to v_k in $\overrightarrow{C}$ (of length k-i), then insert an edge, necessarily of length $(k-i+1)\ell - 1$, from the terminal vertex of P_j,i to the initial vertex of P_j,k. If we do this for each arc in $\overrightarrow{C}$, it is easy to see that the paths of ${\cal P}_j$ 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 $(k-i-1)\ell + 1$, 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 $\overleftarrow{C}$ of $\overrightarrow{C}$ to link the paths in another collection ${\cal P}_t$, $t\neq k$, into an m-cycle. Observe that all the edges used to link together the paths have lengths congruent to $\pm 1$ modulo $\ell$ and thus none of them have been used in the construction of the families $\{{\cal P}_j\;\vert\; 0 \le j \le b-1\}$.

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 ${\cal P}_j$ 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 ${\cal P}_j$, results in some edges of lengths congruent to $\pm 1$ modulo $\ell$ 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₁ and s₂ in G such that gcd (s₁,s₂)=1, which guarantees that the circulant graph with connection set $\{\pm s_1,\pm s_2\}$ 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 $\pm 1$ modulo $\ell$ corresponding to the edges used in the Hamilton cycles. Second, when we are left with 1 or 3 families $\{{\cal P}_j\}$ 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^da' and that 2^da'>2b. We now proceed depending on the number of families $\{{\cal P}_j\}$ to link together. If b=1, then let $G = X(2^da'; \{\pm1\})$ so that Gis a (2^da')-cycle. In this case, the length $2\ell-1$ is used in H to link ${\cal P}_0$ into an m-cycle. If b=3, then G has at least eight vertices so that there are at least two lengths s₁ and s₂ relatively prime to 2^da'. Then each of s₁ and s₂generates a Hamilton cycle in $G = X(2^da'; \{\pm s_1, \pm s_2\})$ and thus we can easily link together the three families of paths into m-cycles. In this case, the lengths $(s_1+1)\ell-1, (s_1-1)\ell+1$, and $(s_2+1)\ell - 1$ are used in H to link ${\cal P}_0, {\cal P}_1, {\cal P}_2$ into m-cycles.

Finally, if b >3, then write b = 4q + 1 or b = 4q + 3 for some positive integer q. Suppose first that b = 4q + 1. Then $X(2^da'; \{\pm 1\})$ can be used to link ${\cal P}_0$ into an m- cycle using the length $2\ell-1$ in H. Next take q successive pairs $\{2,3\}, \{4,5\}, \ldots,\{2q,2q+1\}$, all of which generate connected circulants, to obtain two Hamilton cycles in $X(2^da'; \{\pm 2i, \pm (2i+1)\})$, for $1 \le i \le q$, to link together four families at a time. Then the lengths $3\ell -1, \ell+1, 4\ell-1, 2\ell+1, \ldots, (2q+2)\ell-1, 2q\ell+1$are used in H. If b = 4q + 3, then find a second integer $t \ge 2q+1$ relatively prime to 2^da' to handle the two extra families, and the lengths $(t+1)\ell-1$ and $(t-1)\ell+1$ are used in H.

Upon obtaining all the m-cycles as described above, we then let $\rho$act on each m-cycle C according to $C, \rho(C),\rho^2(C),\ldots, \rho^{\ell-1}(C)$ resulting in a decomposition of $H=X(n-2;B\cup-B)$into m-cycles. This completes the proof of Theorem 1.1.