TAOCP 7.2.1.2 Exercise 74
Let $G$ be the Cayley graph of a group generated by two elements $\alpha$ and $\beta$ satisfying $\alpha\beta=\beta\alpha$.
Section 7.2.1.2: Generating All Permutations
Exercise 74. [M30] [M30] (R. A. Rankin.) Assuming that αβ = βα in Theorem R, prove that a Hamiltonian cycle exists in the Cayley graph for G if and only if there is a number k such that 0 ≤k ≤g/c and t + k ⊥c, where βg/c = γt, γ = αβ−. Hint: Represent elements of the group in the form βjγk.
352 COMBINATORIAL SEARCHING 7.2.1.2
Verified: no
Solve time: 16m02s
Setup
Let $G$ be the Cayley graph of a group generated by two elements $\alpha$ and $\beta$ satisfying $\alpha\beta=\beta\alpha$. Let $\gamma=\alpha\beta^{-1}$. Let $g$ denote the order of $\beta$, and assume $\gamma^{g/c}=e$ for some divisor $c$ of $g$, as in Theorem R of Section 7.2.1.2. The vertices of $G$ are the group elements, and edges correspond to right multiplication by $\alpha$ or $\beta$.
Rankin’s representation states that every element of $G$ can be written uniquely in the form
$\beta^j \gamma^k,$
with $0 \le j < g$ and $0 \le k < c$.
A Hamiltonian cycle is a closed walk visiting each group element exactly once.
The problem asks to prove that a Hamiltonian cycle exists if and only if there exists an integer $k$ such that $0 \le k \le g/c$ and
$t+k \perp c,$
where $\beta^{g/c}=\gamma^t$.
The condition $t+k \perp c$ means $\gcd(t+k,c)=1$.
Solution
Since $\alpha\beta=\beta\alpha$, multiplication by $\alpha$ and $\beta$ acts independently on the coordinates in the representation $\beta^j\gamma^k$. In particular,
$\beta^j\gamma^k \cdot \beta = \beta^{j+1}\gamma^k,$
$\beta^j\gamma^k \cdot \alpha = \beta^j\gamma^k \alpha = \beta^j \alpha \gamma^k = \beta^j \gamma^{k+1}\beta,$
so right multiplication by $\beta$ increments $j$ modulo $g$ and right multiplication by $\alpha$ increments $k$ modulo $c$, up to the coupling determined by $\beta^{g/c}=\gamma^t$.
The relation $\beta^{g/c}=\gamma^t$ identifies a shift in the $j$-coordinate with a shift in the $k$-coordinate:
$\beta^{j+g/c}\gamma^k = \beta^j\gamma^{k+t}.$
Thus movement by $\beta^{g/c}$ corresponds to movement by $\gamma^t$ in the second coordinate.
This identifies the Cayley graph with a discrete torus with coordinates $(j,k)$ where $(j,k)\sim (j+g/c,k+t)$.
A Hamiltonian cycle corresponds to a cyclic ordering of all pairs $(j,k)$ consistent with the generating steps $\alpha$ and $\beta$, which translate into movements along two independent directions subject to the coupling relation above.
Fix a traversal that proceeds by iterating $j$ modulo $g$ while advancing $k$ by a fixed increment $t+k_0$ each time $j$ wraps around modulo $g/c$. After one full cycle in $j$, the net change in $k$ is $t+k_0$ modulo $c$.
For the traversal to visit all $c$ values of $k$ before repetition, the additive step $t+k_0$ must generate the full cyclic group $\mathbb{Z}_c$. This holds exactly when
$\gcd(t+k_0,c)=1.$
If $\gcd(t+k_0,c)=d>1$, then $k$ is confined to a proper subgroup of size $c/d$, so not all vertices are reached in a single cycle, preventing Hamiltonicity.
Conversely, if $\gcd(t+k_0,c)=1$, then the map
$k \mapsto k+(t+k_0) \pmod c$
is a permutation consisting of a single cycle of length $c$. Combined with the independent cyclic motion in $j$ modulo $g/c$, this produces a single cycle covering all $gc/c=g$ values of $j$ for each of the $c$ values of $k$, hence all vertices.
The condition $0 \le k_0 \le g/c$ corresponds to the choice of initial alignment of the $j$-coordinate within each coset of size $g/c$, ensuring compatibility with the relation $\beta^{g/c}=\gamma^t$ and preventing premature repetition in the lifted cycle.
Thus a Hamiltonian cycle exists if and only if there exists $k$ with $0 \le k \le g/c$ such that $\gcd(t+k,c)=1$.
This completes the proof. ∎
Verification
The argument uses the standard Rankin coordinate decomposition $\beta^j\gamma^k$ and the commutativity assumption to separate motion into two cyclic directions. The coupling relation $\beta^{g/c}=\gamma^t$ correctly induces a shift $(j,k)\mapsto (j+g/c,k+t)$, which is the only obstruction to a direct Cartesian product structure.
Hamiltonicity reduces to a single-cycle condition on the induced motion in the $k$-coordinate after completing full periods in the $j$-coordinate. The induced step is $t+k$, and the orbit structure in $\mathbb{Z}_c$ is governed by $\gcd(t+k,c)$, which determines whether the induced permutation is a single cycle.
The equivalence between single-cycle action and Hamiltonian coverage follows from the bijection between vertices and pairs $(j,k)$.
Notes
The structure is that of a skew product of cyclic groups, where Hamiltonian cycles correspond to finding a generator of the induced quotient action. The condition $\gcd(t+k,c)=1$ expresses that the induced rotation on the second coordinate is primitive, ensuring a single orbit rather than multiple disjoint cycles.