$SB(3,n)$ has no Hamiltonian cycle when $n$ is even: a sign-of-permutation proof, with extension to all odd $m\equiv 3(\mathrm{mod}4)$

Abstract

We resolve exercise 7.2.2.4--224 of Knuth's Pre-Fascicle 8a (10 April 2026 draft, rated [46]): the digraph $SB(3,n)$ has no Hamiltonian cycle when $n$ is even. The argument is a sign-of-permutation obstruction. Writing the successor map of a candidate Hamiltonian cycle as $f_S=A_b\circ \sigma$, $\mathrm{sgn}(A_b)=+1$ when $m$ is odd, so $\mathrm{sgn}(f_S)=\mathrm{sgn}(\sigma )$ for every choice set $S$. A short dihedral Burnside computation shows $\mathrm{sgn}(\sigma )=-1$ on ${\Sigma }_3^n$ for even $n$, contradicting the sign $+1$ required of a single $3^n$-cycle. The same argument gives the stronger statement that $SB(m,n)$ has no Hamiltonian cycle whenever $m$ is odd with $m\equiv 3(\mathrm{mod}4)$ and $n$ is even; this restricts the residue classes in which Knuth's hint to Ex.~225 (existence of Hamiltonian cycles in $SB(m,n)$ for all $m>3$ and $n>2$) can hold.

15 pages. Resolves Exercise 7.2.2.4--224 of D. E. Knuth, TAOCP Vol. 4, Pre-Fascicle 8a (rated [46]). Main theorem extends to all odd $m\equiv 3(\mathrm{mod}4)$