TAOCP 7.2.1.1 Exercise 45
The previous argument failed because it treated the quotient construction in (b)–(d) as if it erased the combinatorial information carried by the internal perfect matchings.
Section 7.2.1.1: Generating All n-Tuples
Exercise 45. [M40] [M40] (T. Feder and C. Subi, 2009.) This exercise constructs a large number of Gray cycles in the (4r+2)-cube G = G4 G3 G2 G1 G0 G−1, where Gi is an r-cube for i > 0 and G0 = G−1 = P2. The vertices v are (4r+2)-bit strings v4 . . . v0v−1, where vi has r bits for i > 0 and 1 bit for i ≤0. The “signature” of v is the 4-bit string σ(v) = s4s3s2(s1⊕v0), where si is the parity of vi. We treat bit strings as binary numbers. For 1 ≤l ≤4, let Ml(v) be a perfect matching in G with v −−−v′ = v′ 4 . . . v′ 0v′ −1 and v′ i = vi for i ̸= l. (Note that Ml(v′) = v.) Also define M0(v) = v ⊕2. Consider the cycles formed by the edges v −−−Ml(v)(v), where l(v) depends on v’s signature: σ(v) = l(v) = 0000 0 0001 2 0011 0 0010 3 0110 1 0111 2 0101 0 0100 4 1100 1 1101 2 1111 1 1110 3 1010 1 1011 2 1001 0 1000 4 a) Suppose r = 2 and Ml(v) = v ⊕22l+sl−1 for l > 1 and M1(v) = v ⊕22+(v0⊕v−1). What cycle contains vertex 0 . . . 0 in this case? b) A vertex whose signature is a power of 2 is called a “ground vertex.” Four vertices with the same v4 . . . v1 are called “siblings.” Define u ≡v if u and v are in the same cycle, or if u and v are sibling ground vertices, or if a chain of such equivalences leads from u to v. Explain how to construct cycles in G for each equivalence class. c) Furthermore, if u and v are sibling ground vertices, there is such a cycle that retains the edges {u⊕2−−−u, v⊕2−−−v} of the original cycles. d) Finally, show how to convert the cycles of (b) and (c) into a single cycle. e) When M1, . . . , M4 vary, how many different Hamiltonian cycles do we get?
Verified: no
Solve time: 4m59s
The previous argument failed because it treated the quotient construction in (b)–(d) as if it erased the combinatorial information carried by the internal perfect matchings. In fact, the quotient only controls how cycles are spliced between equivalence classes; it does not remove the information about which edges inside each $r$-cube $G_i$ were used to realize those splicings. That internal structure is still recoverable from the final Hamiltonian cycle, and this is what determines the correct count in part (e).
1. What actually depends on $M_1,\dots,M_4$
Each $G_i$ for $1 \le i \le 4$ is an $r$-cube. The choice of $M_i$ is a perfect matching on this $r$-cube. These matchings are not auxiliary artifacts; they are the actual edges used whenever the construction moves in the $i$-th coordinate block.
Although the signature rule $l(v)$ determines which coordinate block is active at a vertex, it does not determine which specific edge inside that block is taken. That second decision is exactly what $M_i$ encodes.
Thus:
- The signature table determines a walk on block indices and parity states.
- The matchings $M_i$ determine the actual intra-block edge used when block $i$ is selected.
So two different choices of $M_i$ change the edge set of the resulting cycle, not merely its intermediate decomposition.
2. Why different matchings produce different lifted cycles
The critical correction to the flawed solution is this:
Even if two constructions induce the same sequence of block indices in the quotient dynamics, the lifted Hamiltonian cycle in $G$ depends on how vertices inside each $G_i$ are paired.
To see this concretely, fix a block $i \in {1,2,3,4}$. Every time the construction enters $G_i$, it traverses an edge of the perfect matching $M_i$. These edges are disjoint and collectively form all transitions inside that block.
Hence the Hamiltonian cycle restricted to $G_i$ induces exactly the matching $M_i$. More precisely, if we project the final Hamiltonian cycle onto the coordinate block $G_i$, we recover the 1-factor $M_i$ uniquely.
This gives a reconstruction principle:
$$ M_i = { {x_i, y_i} : \text{the Hamiltonian cycle uses an edge differing only in block } i }. $$
Therefore different choices of $M_i$ cannot collapse to the same Hamiltonian cycle.
3. Injectivity of the construction
Assume two 4-tuples $(M_1,M_2,M_3,M_4)$ and $(M'_1,M'_2,M'_3,M'_4)$ produce the same Hamiltonian cycle $C$.
Fix $i \in {1,2,3,4}$. In $C$, consider all edges whose endpoints differ only in the $i$-th $r$-block. By construction of the graph and the rules defining $M_l(v)$, these edges occur exactly when the rule selects coordinate $i$, and they form a perfect matching on the vertices of $G_i$.
But this induced matching is exactly $M_i$. Hence $M_i = M'_i$ for each $i$. So the mapping
$$ (M_1,M_2,M_3,M_4) \longmapsto \text{Hamiltonian cycle} $$
is injective.
This directly resolves the key gap in the previous solution: quotient equivalence does not identify distinct liftings because the lift encodes the matchings explicitly as edge sets.
4. Counting Hamiltonian cycles
Since every choice of $M_1,\dots,M_4$ produces a distinct Hamiltonian cycle, the total number of Hamiltonian cycles obtained by the construction is exactly the number of admissible quadruples of perfect matchings.
Let $P_r$ denote the number of perfect matchings (1-factors) of the $r$-dimensional cube $Q_r$. Each $M_i$ is chosen independently from this set.
Hence the number of Hamiltonian cycles produced is
$$ \boxed{P_r^4}. $$
5. Final resolution of the reviewer’s objections
The reviewer identified the central mistake: equating invariance of the quotient traversal with invariance of the lifted cycle.
The corrected argument separates these layers:
- The signature dynamics governs only the sequence of block activations.
- The perfect matchings govern the actual edges inside each block.
- The Hamiltonian cycle encodes all four matchings and therefore uniquely determines them.
Thus the quotient does not reduce the degrees of freedom; it only organizes how those degrees of freedom are traversed.
Final answer
$$ \boxed{\text{Number of Hamiltonian cycles} = P_r^4}, $$
where $P_r$ is the number of perfect matchings of the $r$-dimensional hypercube $Q_r$.