# On Cayley Digraphs That Do Not Have Hamiltonian Paths

Authors: Dave Witte Morris
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

We construct an infinite family{Cay→(Gi;ai;bi)} of connected, 2-generated Cayley digraphs that do not have hamiltonian paths, such that the orders of the generators ai and bi are unbounded. We also prove that if G is any finite group with |[G,G]|≤3, then every connected Cayley digraph on G has a hamiltonian path (but the conclusion does not always hold when |[G,G]|=4 or 5).


---

## Body

## 1. Introduction

Definition 1.
For a subsetS of a finite group G, the Cayley digraph  Cay→(G;S) is the directed graph whose vertices are the elements of G and with a directed edge g→gs for every g∈G and s∈S. The corresponding Cayley graph is the underlying undirected graph that is obtained by removing the orientations from all the directed edges.It has been conjectured that every (nontrivial) connected Cayley graph has a hamiltonian cycle. (See the bibliography of [1] for some of the literature on this problem.) This conjecture does not extend to the directed case, because there are many examples of connected Cayley digraphs that do not have hamiltonian cycles. In fact, infinitely many Cayley digraphs do not even have a hamiltonian path.Proposition 2 (attributed to Milnor [2, p. 201]).
Assume the finite groupG is generated by two elements a and b, such that a2=b3=e. If |G|≥9|ab2|, then the Cayley digraph Cay→(G;a,b) does not have a hamiltonian path.The examples in the above proposition are very constrained, because the order of one generator must be exactly 2 and the order of the other generator must be exactly 3. In this note, we provide an infinite family of examples in which the orders of the generators are not restricted in this way. In fact,a and b can both be of arbitrarily large order.Theorem 3.
For anyn∈ℕ, there is a connected Cayley digraph Cay→(G;a,b), such that(1)
Cay→(G;a,b) does not have a hamiltonian path,(2)
a and b both have order greater than n.Furthermore, if p is any prime number such that p>3 and p≡3(mod4), then we may construct the example so that the commutator subgroup of G has order p. More precisely, G=ℤm⋉ℤp is a semidirect product of two cyclic groups, so G is metacyclic.Remark 4.
Here are some related open questions and other comments.(1)
The above results show that connected Cayley digraphs on solvable groups do not always have hamiltonian paths. On the other hand, it is an open question whether connected Cayley digraphs onnilpotent groups always have hamiltonian paths.  (See [3] for recent results on the nilpotent case.)(2)
The above results always produce a digraph with an even number of vertices. Do there exist infinitely many connected Cayley digraphs of odd order that do not have hamiltonian paths?(3)
We conjecture that the assumption “p≡3 (mod 4)” can be eliminated from the statement of Theorem 3. On the other hand, it is necessary to require that p>3  (see Corollary 16).(4)
IfG is abelian, then it is easy to show that every connected Cayley digraph on G has a hamiltonian path. However, some abelian Cayley digraphs do not have a hamiltonian cycle. See  Section 5 for more discussion of this.(5)
The proof of Theorem3 appears in Section 3, after some preliminaries in Section 2.


## 2. Preliminaries

We recall some standard notation, terminology, and basic facts.Notation. Let G be a group, and let H be a subgroup of G. (All groups in this paper are assumed to be finite.)(i)
e is the identity element of G;(ii)
xg=g-1xg, for x,g∈G;(iii)
we writeH⊴G to say that H is a normal subgroup of G;(iv)
HG=〈hg∣h∈H,g∈G〉 is the normal closure of H in G, so HG⊴G.Definition 5.
LetS be a subset of the group G.(i)
H=〈SS-1〉 is the arc-forcing subgroup, where SS-1={st-1∣s,t∈S}.(ii)
For anya∈S, a-1H is called the terminal coset. (This is independent of the choice of a.)(iii)
Any left coset ofH that is not the terminal coset is called a regular coset.(iv)
Forg∈G and s1,…,sn∈S, we use [g](si)i=1n to denote the walk in Cay→(G;S) that visits (in order) the vertices
(1)g,gs1,gs1s2,…,gs1s2⋯sn.We usually omit the prefix[g] when g=e. Also, we often abuse notation when sequences are to be concatenated. For example,
(2)(a4,(si)i=13,tj)j=12=(a,a,a,a,s1,s2,s3,t1,a,a,a,a,s1,s2,s3,t2).Remark 6.
Here are two observations about the arc-forcing subgroup.(1)
It is important to note that〈SS-1〉⊆〈Sg〉, for every g∈G. Furthermore, we have 〈SS-1〉=〈Sa-1〉, for every a∈S.(2)
It is sometimes more convenient to define the arc-forcing subgroup to be〈S-1S〉, instead of 〈SS-1〉 (e.g., this is the convention used in [3, p. 42]). The difference is minor, because the two subgroups are conjugate: for any a∈S, we have
(3)〈S-1S〉=〈a-1S〉=〈Sa-1〉a=〈SS-1〉a.Definition 7.
SupposeL is a hamiltonian path in a Cayley digraph Cay→(G;S) and s∈S.(i)
A vertexg∈G  travels by  s if L contains the directed edge g→gs.(ii)
A subsetX of G  travels by  s if every element of X travels by s.Lemma 8 (see Housman [4, p. 82]).
SupposeL is a hamiltonian path in Cay→(G;a,b), with initial vertex e, and let H=〈ab-1〉 be the arc-forcing subgroup. Then,(1)
the terminal vertex ofL belongs to the terminal coset a-1H,(2)
each regular coset either travels bya or travels by b.


## 3. Proof of Theorem3

Let(i)
α be an even number that is relatively prime to (p-1)/2, with α>n;(ii)
β a multiple of (p-1)/2 that is relatively prime to α, with β>n;(iii)
a¯ a generator of ℤα;(iv)
b¯ a generator of ℤβ;(v)
z a generator of ℤp;(vi)
r a primitive root modulo p;(vii)
G=(ℤα×ℤβ)⋉ℤp, where za¯=z-1 and zb¯=zr2;(viii)
a=a¯z, so |a|=α, and a inverts ℤp;(ix)
b=b¯z, so |b|=β, and b acts on ℤp via an automorphism of order (p-1)/2;(x)
H=〈ab-1〉=〈a¯b¯-1〉=ℤα×ℤβ. Suppose L is a hamiltonian path in Cay→(G;a,b). This will lead to a contradiction.It is well known (and easy to see) that Cayley digraphs are vertex-transitive, so there is no harm in assuming that the initial vertex ofL is e. Note that(i)
the terminal coset isa-1H=z-1H;(ii)
sincep≡3(mod4), we have ℤp×=〈-1,r2〉.Case 1.
Assume at most one regular coset travels bya in L.  Choose z′∈ℤp, such that z′H is a regular coset, and assume it is the coset that travels by a, if such exists.
Forg∈G, let
(4)ℬg={gbkH∣k∈ℤ}.
Letting p′=(p-1)/2, we have
(5)(r2)p′-1+(r2)p′-2+⋯+(r2)1+1=(r2)p′-1r2-1=rp-1-1r2-1≡0(modp),
so
(6)b(p-1)/2=(b¯z)p′=b¯p′z(r2)p′-1+(r2)p′-2+⋯+(r2)1+1=b¯p′∈ℤα×ℤβ=H.
Therefore #ℬe≤(p-1)/2≤p-2, so we can choose two cosets ziH and zjH that do not belong to ℬe.
Recall that, by definition,z′H is not the terminal coset z-1H, so z′z is a nontrivial element of ℤp. Then, since ℤp×=〈-1,r2〉, we can choose some h∈〈a¯,b¯〉=H, such that (zj-i)h=z′z. Now, since
(7)ziH,zjH∉ℬe,z-1h-1zj-i∈z-1(zj-i)hH=z-1(z′z)H=z′H,
we may multiply on the left by g=z-1h-1z-i to see that
(8)z-1H,z′H∉ℬg.
Therefore, no element of ℬg is either the terminal coset or the regular coset that travels by a. This means that every coset in ℬg travels by b, so L contains the cycle [g](bβ), which contradicts the fact that L is a (hamiltonian) path.Case 2.
Assume at least two regular cosets travel bya in L.   Let ziH and zjH be two regular cosets that both travel by a. Since ℤp×=〈-1,r2〉, we can choose some h∈〈a¯,b¯〉=H, such that (z-1)h=zj-i.
Note thatzih-1ak travels by a, for every k∈ℤ.(i)
Ifk=2ℓ is even, then
(9)ak=(a¯z)2ℓ=(a¯za¯z)ℓ=(a¯2za¯z)ℓ=(a¯2z-1z)ℓ=a¯2ℓ∈H,
so zih-1ak∈ziH travels by a.(ii)
Ifk=2ℓ+1 is odd, then
(10)ak=(a¯z)2ℓ+1=(a¯z)2ℓ(a¯z)=a¯2ℓ(a¯z)=a¯kz,
so
(11)zih-1ak=zih-1(a¯kz)=zih-1z-1a¯k=zi(z-1)hh-1a¯k∈zi(zj-i)H=zjH
travels by a. Therefore L contains the cycle [zih-1](aα), which contradicts the fact that L is a (hamiltonian) path.


## 4. Cyclic Commutator Subgroups of Very Small Order

It is known that if|[G,G]|=2, then every connected Cayley digraph on G has a hamiltonian path. (Namely, we have [G,G]⊆Z(G), so G is nilpotent, and the conclusion, therefore, follows from Theorem 14(2) below.) In this section, we prove the same conclusion when |[G,G]|=3. We also provide counterexamples to show that the conclusion is not always true when |[G,G]|=4 or |[G,G]|=5.We begin with several lemmas. The first three each provide a way to convert a hamiltonian path in a Cayley digraph on an appropriate subgroup ofG to a hamiltonian path in a Cayley digraph on all of G.Lemma 9.
Assume(i)
G is a finite group, such that [G,G]≅ℤpk, where p is prime and k∈ℕ;(ii)
S is a generating set for G;(iii)
a,b∈S, such that 〈[a,b]〉=[G,G];(iv)
N=〈a,b〉. If Cay→(N;a,b) has a hamiltonian path, then Cay→(G;S) has a hamiltonian path.Proof.
Since[G,G]⊆N, we know that G/N is an abelian group, so there is a hamiltonian path (si)i=1m in Cay→(G/N;S)  (see Proposition 19 below). Also, by assumption, there is a hamiltonian path (tj)j=1n in Cay→(N;a,b). Then
(12)(((tj)j=1n,si)i=1m,(tj)j=1n)
is a hamiltonian path in Cay→(G;S).Definition 10.
IfK is a subgroup of G, then K∖Cay→(G;S) denotes the digraph whose vertices are the right cosets of K in G and with a directed edge Kg→Kgs for each g∈G and s∈S. Note that K∖Cay→(G;S)=Cay→(G/K;S) if K⊴G.Lemma 11 (“Skewed-Generators Argument,” cf. [3, Lem. 2.6], [5, Lem. 5.1]).
Assume(i)
S is a generating set for the group G;(ii)
K is a subgroup of G, such that every connected Cayley digraph on K has a hamiltonian path;(iii)
(si)i=1n is a hamiltonian cycle in K∖Cay→(G;S);(iv)
〈Ss2s3⋯sn〉=K. Then Cay→(G;S) has a hamiltonian path.Proof.
Since〈Ss2s3⋯sn〉=K, we know that Cay→(K;Ss2s3⋯sn) is connected, so, by assumption, it has a hamiltonian path (tjs2s3⋯sn)j=1m. Then
(13)((tj,(si)i=2n)j=1m-1,tm,(si)i=2n-1)
is a hamiltonian path in Cay→(G;S).Lemma 12.
Assume(i)
S is a generating set of G, with arc-forcing subgroup H=〈SS-1〉;(ii)
there is a hamiltonian path in every connected Cayley digraph onHG;(iii)
eitherH=HG, or H is contained in a unique maximal subgroup of HG. Then Cay→(G;S) has a hamiltonian path.Proof.
It suffices to show that(*)thereexistsahamiltoniancycle(si)i=1ninCay→(GHG;S),suchthatHG=〈Ss2⋯sn〉,
for then Lemma 11 provides the desired hamiltonian path in Cay→(G;S).
IfHG=H, then every hamiltonian cycle in Cay→(G/HG;S) satisfies  (*)  (see Remark 6 (1)). Thus, we may assume HG≠H, so, by assumption, H is contained in a unique maximal subgroup M of HG. Since HG is generated by conjugates of S-1S  (see Remark 6 (2)), there exist a,b,c∈S, such that (a-1b)c∉M.
We may also assumeHG≠G (since, by assumption, every Cayley digraph on HG has a hamiltonian path), so, letting n=|G:HG|≥2, we have the two hamiltonian cycles (an-1,c) and (an-2,b,c) in Cay→(G/HG;S). Since
(14)(an-1c)-1(an-2bc)=(a-1b)c∉M,
the two products an-1c and an-2bc cannot both belong to M. Hence, either (an-1,c) or (an-2,b,c) is a hamiltonian cycle (si)i=1n in Cay→(G/HG;S), such that s1s2⋯sn∉M. Since M is the unique maximal subgroup of HG that contains H, this implies
(15)HG=〈H,s1s2⋯sn〉=〈Ss2s3⋯sn〉,
as desired.The final hypothesis of the preceding lemma is automatically satisfied when[G,G] is cyclic of prime-power order.Lemma 13.
If[G,G] is cyclic of order pk, where p is prime, and H is any subgroup of G, then either H=HG or H is contained in a unique maximal subgroup of HG.Proof.
Note that the normal closureHG is the (unique) smallest normal subgroup of G that contains H. Therefore, HG⊆H[G,G] (since H[G,G] is normal in G). This implies that if M is any proper subgroup of HG that contains H, then
(16)M=H·(M∩[G,G])⊆H·(HG∩[G,G])p.
Therefore, H·(HG∩[G,G])p is the unique maximal subgroup of HG that contains M.The following known result handles the case whereG is nilpotent.Theorem 14 (see Morris [3]).
AssumeG is nilpotent, and S generates G. If either(1)
#S≤2 or(2)
|[G,G]|=pk, where p is prime and k∈ℕ, then Cay→(G;S) has a hamiltonian path.We now state the main result of this section.Theorem 15.
Suppose(i)
[G,G] is cyclic of prime-power order,(ii)
every element ofG either centralizes [G,G] or inverts it. Then every connected Cayley digraph on G has a hamiltonian path.Proof.
LetS be a generating set for G. Write [G,G]=ℤpk for some p and k. Since every minimal generating set of ℤpk has only one element, there exist a,b∈S, such that 〈[a,b]〉=[G,G]. Then, by Lemma 9, we may assume S={a,b}.
LetH=〈ba-1〉 be the arc-forcing subgroup. We may assume HG=G, for otherwise we could assume, by induction on |G|, that every connected Cayley digraph on HG has a hamiltonian path, and then Lemma 12 would apply (since Lemma 13 verifies the remaining hypothesis). So
(17)Hℤpk=H[G,G]⊃HG=G.
Ifa and b both invert ℤpk, then H=〈ba-1〉 centralizes ℤpk=[G,G], so G is nilpotent. Then Theorem 14 applies.
Therefore, we may now assume thata does not invert ℤpk. Then, by assumption, a centralizes ℤpk. Let n=|G:H|, and write a=a¯z, where a¯∈H and z∈ℤpk. Then a=a¯z∈Hz and b=(ba-1)(a¯z)∈Hz. Since 〈a,b〉=G, this implies H〈z〉=G. Therefore,
(18)[H](an)=[H,Hz,Hz2,…,Hzn-1,H]
is a hamiltonian cycle in H∖Cay→(G;S), so Lemma 11 applies.Corollary 16.
If|[G,G]|≤3 or [G,G]≅ℤ4, then every connected Cayley digraph on G has a hamiltonian path.Proof.
Theorem15 applies, because the groups {e} and ℤ2 have no nontrivial automorphisms, and inversion is the only nontrivial automorphism of ℤ3 or ℤ4.Remark 17 ([6, p. 266]).
In the statement of Corollary16, the assumption that [G,G]≅ℤ4 cannot be replaced with the weaker assumption that |[G,G]|=4. For a counterexample, let G=A4×ℤ2. Then |[G,G]|=4, but it can be shown without much difficulty that Cay→(G;a,b) does not have a hamiltonian path when a=((12)(34),1) and b=((123),0).Here is a counterexample when|[G,G]|=5.Example 18.
LetG=ℤ12⋉ℤ5=〈h〉⋉〈z〉, where zh=z3. Then |[G,G]|=5, and the Cayley digraph Cay→(G;h2z,h3z) is connected but does not have a hamiltonian path.Proof.
A computer search can confirm the nonexistence of a hamiltonian path very quickly, but, for completeness, we provide a human-readable proof.
Leta=h2z=z4h2 and b=h3z=z3h3. The argument in Case 2 of the proof of Theorem 3 shows that no more than one regular coset travels by a in any hamiltonian path. On the other hand, since a hamiltonian path cannot contain any cycle of the form [g](b4), we know that at least ⌊(|G|-1)/4⌋=14 vertices must travel by a. Since |ab-1|=12<14, this implies that some regular coset travels by a. So exactly one regular coset travels by a in any hamiltonian path.
For0≤i≤3 and 0≤m≤11, let Li,m be the spanning subdigraph of Cay→(G;a,b) in which(i)
all vertices have outvalence1, except b-1(ab-1)m=z4h9-m, which has outvalence 0;(ii)
the vertices in the regular cosetziH travel by a;(iii)
a vertexb-1h-j=z4h9-j in the terminal coset travels by a if 0≤j<m;(iv)
all other vertices travel byb. An observation of D. Housman [7, Lem. 6.4(b)] tells us that if L is a hamiltonian path from e to b-1(ab-1)m, in which ziH is the regular coset that travels by a, then L=Li,m. Thus, from the conclusion of the preceding paragraph, we see that every hamiltonian path (with initial vertex e) must be equal to Li,m, for some i and m.
However,Li,m is not a (hamiltonian) path. More precisely, for each possible value of i and m, the following list displays a cycle that is contained in Li,m:(i)
ifi=0 and 0≤m≤8,
(19)z2h3⟶bzh6⟶bz3h9⟶bz4⟶bz2h3;(ii)
ifi=0 and 9≤m≤11,
(20)h2⟶azh4⟶bz4h7⟶azh9⟶bz2⟶bh3⟶az2h5⟶bz3h8⟶bzh11⟶bh2;(iii)
ifi=1 and 0≤m≤7,
(21)h4⟶bz3h7⟶bz2h10⟶bz4h⟶bh4;(iv)
ifi=1 and 8≤m≤11,
(22)h⟶bzh4⟶ah6⟶bz2h9⟶bz3⟶bzh3⟶az3h5⟶bz4h8⟶az3h10⟶bh;(v)
ifi=2 and 0≤m≤9,
(23)h5⟶bzh8⟶bz4h11⟶bz3h2⟶bh5;(vi)
ifi=2 and 10≤m≤11,
(24)z2h3⟶az4h5⟶az2h7⟶az4h9⟶az2h11⟶az4h⟶az2h3;(vii)
ifi=3 and 0≤m≤10:
(25)h7⟶bz4h10⟶bzh⟶bz2h4⟶bh7;(viii)
ifi=3 and m=11,
(26)z3h2⟶az4h4⟶az3h6⟶az4h8⟶az3h10⟶az4⟶az3h2.Since Li,m is never a hamiltonian path, we conclude that Cay→(G;a,b) does not have a hamiltonian path.


## 5. Nonhamiltonian Cayley Digraphs on Abelian Groups

WhenG is abelian, it is easy to find a hamiltonian path in Cay→(G;S).Proposition 19 (see [6, Thm. 3.1]).
Every connected Cayley digraph on any abelian group has a hamiltonian path.On the other hand, it follows from Lemma8(2) that sometimes there is no hamiltonian cycle.Proposition 20 (see Rankin [8, Thm. 4]).
AssumeG=〈a,b〉 is abelian. Then there is a hamiltonian cycle in Cay→(G;a,b) if and only if there exist k,ℓ≥0, such that 〈akbℓ〉=〈ab-1〉, and k+ℓ=|G:〈ab-1〉|.Example 21.
Ifgcd(a,n)>1 and gcd(a+1,n)>1, then Cay→(ℤn;a,a+1) does not have a hamiltonian cycle.All of the non-hamiltonian Cayley digraphs provided by Proposition20 are 2-generated. However, a few 3-generated examples are also known. Specifically, the following result lists (up to isomorphism) the only known examples of connected, non-hamiltonian Cayley digraphs Cay→(G;S), such that #S>2 (and e∉S).Theorem 22 (see Locke and Witte [9]).
The following Cayley digraphs do not have hamiltonian cycles:(1)
Cay→(ℤ12k;6k,6k+2,6k+3), for any k∈ℤ+;(2)
Cay→(ℤ2k;a,b,b+k), for a,b,k∈ℤ+, such that certain technical conditions  (Remark 23) are satisfied.Remark 23.
The precise conditions in  (2) are (i) eithera or k is odd, (ii) either a is even or b and k are both even, (iii) gcd(a-b,k)=1, (iv) gcd(a,2k)≠1, and (v) gcd(b,k)≠1.It is interesting to note that, in the examples provided by Theorem22, the group G is cyclic (either ℤ12k or ℤ2k), and either(1)
one of the generators has order2 or(2)
two of the generators differ by an element of order2.S. J. Curran (personal communication) asked whether the constructions could be generalized by allowing G to be an abelian group that is not cyclic. We provide a negative answer for case  (2).Proposition 24.
LetG be an abelian group (written additively), and let a,b,k∈G, such that k is an element of order 2. (Also assume {a,b,b+k} consists of three distinct, nontrivial elements of G.) If the Cayley digraph Cay→(G;a,b,b+k) is connected, but does not have a hamiltonian cycle, then G is cyclic.Proof.
We prove the contrapositive: assumeG is not cyclic, and we will show that the Cayley digraph has a hamiltonian cycle (if it is connected). The argument is a modification of the proof of [9, Thm. 4.1(⇐)].
Construct a subdigraphH0 of G as in [9, Defn. 4.2], but with G in the place of ℤ2k, with |G| in the place of 2k, and with |a| in the place of d. (Case 1 is when k∉〈a〉; Case 2 is when k∈〈a〉.) Every vertex of H0 has both invalence 1 and outvalence 1.
The argument in case 3 of the proof of [9, Thm. 4.1(⇐)] shows that the Cayley digraph Cay→(G;a,b,b+k) has a hamiltonian cycle if 〈a-b,k〉≠G. Therefore, we may assume 〈a-b,k〉=G. On the other hand, we know 〈a-b〉≠G (because G is not cyclic). Since |k|=2, this implies G=〈a-b〉⊕〈k〉. Since G is not cyclic, this implies that a-b has even order. Also, we may write a=a′+k′ and b=b′+k′′ for some (unique) a′,b′∈〈a-b〉 and k′,k′′∈〈k〉. (Since a′-b′∈〈a-b〉, it is easy to see that k′=k′′, but we do not need this fact.)
Claim.
H
0 has an odd number of connected components.  Arguing as in the proof of [9, Lem. 4.1] (except that, as before, Case 1 is when k∉〈a〉 and Case 2 is when k∈〈a〉), we see that the number of connected components in H0 is
(27)|G:〈a,k〉|+|G:〈b,k〉|ifk∉〈a〉,|G:〈b,k〉|ifk∈〈a〉.
Since 〈a′-b′〉=〈a-b〉, we know that one of a′ and b′ is an even multiple of a-b, and the other is an odd multiple. (Otherwise, the difference would be an even multiple of a-b, so it would not generate 〈a-b〉.) Thus, one of |G:〈a,k〉| and |G:〈b,k〉| is even, and the other is odd. So |G:〈a,k〉|+|G:〈b,k〉| is odd. This establishes the claim if k∉〈a〉.
We may now assumek∈〈a〉. This implies that the element a′ has odd order (and k′ must be nontrivial, but we do not need this fact). This means that a′ is an even multiple of a-b, so b′ must be an odd multiple of a-b (since 〈a′-b′〉=〈a-b〉). Therefore, |〈a-b〉:〈b′〉| is odd, which means |G:〈b,k〉| is odd. This completes the proof of the claim.
Now, if|G:〈b,k〉| is odd, we can apply a very slight modification of the argument in case 4 of the proof of [9, Thm. 4.1(⇐)]. (Subcase 4.1 is when k∉〈a〉 and subcase 4.2 is when k∈〈a〉.) We conclude that Cay→(G;a,b,b+k) has a hamiltonian cycle, as desired.
Finally, if|G:〈b,k〉| is even, then more substantial modifications to the argument in [9] are required. For convenience, let m=|G:〈a,k〉|. Note that, since |G:〈b,k〉| is even, the proof of the claim shows that m is odd and k∉〈a〉.
DefineH0′ as in subcase 4.1 of [9, Thm. 4.1(⇐)] (with G in the place of ℤ2k and replacing gcd(b,k) with |G:〈b,k〉|). Let H1=H0′, and inductively construct, for 1≤i≤(m+1)/2, an element Hi of ℰ, such that
(28){v∣zv=0,0≤yv≤2i-2}∪{v∣zv=1,xv=0or1(mod|G:〈b,k〉|)}
is a component of Hi, and all other components are components of H0. The construction of Hi from Hi-1 is the same as in subcase 4.1, but with 2i replaced by 2i-1.
We now letK1=H(m+1)/2 and inductively construct, for 1≤i≤|G:〈b,k〉|/2, an element Ki of ℰ, such that
(29){v∣zv=0}∪{v∣zv=1,xv≡0,1,…,or2i-1(mod|G:〈b,k〉|)}
is a single component of Ki. Namely, [9, Lem. 4.2] implies there is an element Ki=Ki-1′, such that (2i-2)a, (2i-2)a+k, and (2i-1)a+k are all in the same component of Ki. Then, for i=|G:〈b,k〉|/2, we see that Ki is a hamiltonian cycle.



---

*Source: 725809-2013-12-26.xml*