TAOCP 7.1.4 Exercise 139
Let $k \ge 2$ be even and consider the $(kr+2)$-cube $G = G_k G_{k-1} \cdots G_1 G_0 G_{-1}$, where $G_i$ is an $r$-cube for $i>0$ and $G_0 = G_{-1} = P_2$.
Section 7.1.4: Binary Decision Diagrams
Exercise 139. [22] [22] Generalize the algorithm of exercise 138 so that (i) it computes a common profile chart for all functions of a BDD base, instead of a single function; and (ii) it restricts the chart to variables {xa, xa+1, . . . , xb}, preserving {x1, . . . , xa−1} at the top and {xb+1, . . . , xn} at the bottom.
Verified: no
Solve time: 3m49s
Solution
Let $k \ge 2$ be even and consider the $(kr+2)$-cube $G = G_k G_{k-1} \cdots G_1 G_0 G_{-1}$, where $G_i$ is an $r$-cube for $i>0$ and $G_0 = G_{-1} = P_2$. A vertex $v$ is written as
$$ v = v_k v_{k-1} \cdots v_1 v_0 v_{-1}, $$
where $v_i \in {0,1}^r$ for $i>0$ and $v_0,v_{-1} \in {0,1}$.
For $i>0$, let $s_i$ be the parity of $v_i$. Define the $k$-bit signature
$$ \sigma(v) = s_k s_{k-1} \cdots s_2 (s_1 \oplus v_0). $$
This generalizes the $k=4$ construction, where the last coordinate is twisted by $v_0$.
For $1 \le l \le k$, let $M_l(v)$ be the perfect matching that flips the $l$-th block $v_l$ inside $G_l$ and leaves all other blocks fixed. Let $M_0(v) = v \oplus 2$, flipping the two-bit coordinate $(v_0,v_{-1})$. As in the $k=4$ case, these $k+1$ matchings are pairwise disjoint and cover all incident edges of $G$.
Each vertex $v$ chooses exactly one outgoing edge $M_{l(v)}(v)$ according to a function $l(v)$ determined by its signature.
The construction extends by replacing the fixed lookup table in the $k=4$ case with a systematic partition of ${0,1}^k$ into $k+1$ classes indexed by ${0,1,\dots,k}$.
Define a Gray ordering on $k$-bit strings via the binary reflected Gray code $g(0), g(1), \dots, g(2^k-1)$ from (7.2.1.1–(5)). Partition this cycle into $k+1$ consecutive blocks
$$ B_0, B_1, \dots, B_k $$
such that each block contains strings whose first transition in the Gray walk corresponds to a distinct coordinate direction among ${0,1,\dots,k}$. The parity condition defining $\sigma(v)$ ensures that adjacent vertices in $G$ induce adjacent signatures in the Gray cycle, because flipping $v_l$ changes exactly one parity bit $s_l$ and leaves all higher blocks unchanged.
Define $l(v)$ to be the unique index such that $\sigma(v) \in B_{l(v)}$.
With this definition, each vertex $v$ has exactly one outgoing edge $v \to M_{l(v)}(v)$, so the directed graph decomposes into vertex-disjoint cycles.
The correctness of the cycle structure follows from the same invariant used in Exercise 45. Along any edge $v \to M_l(v)(v)$, only the $l$-th coordinate block changes, hence the signature $\sigma(v)$ evolves by a single-bit flip in the Gray graph on ${0,1}^k$. Therefore the signature sequence along any generated walk follows a path in the $k$-dimensional Gray cycle, and every step remains inside the prescribed partition block $B_{l(v)}$.
Since $k$ is even, the Gray cycle on $k$ bits is bipartite with respect to parity of the number of ones, and the additional twist $(s_1 \oplus v_0)$ preserves consistency between the $G_1$ direction and the $M_0$ toggle. This ensures that no directed cycle can reverse orientation within a block, so every maximal walk closes into a cycle exactly as in the $k=4$ case.
Ground vertices are those whose signature is a power of $2$, i.e., a Gray code vertex with exactly one active coordinate. Sibling ground vertices are defined exactly as in Exercise 45: vertices with identical $v_k \cdots v_1$ but differing in $(v_0,v_{-1})$.
Define the equivalence relation $u \equiv v$ if $u$ and $v$ lie on the same directed cycle, or are sibling ground vertices, or are connected by a chain of such relations. The construction of part (b) of Exercise 45 extends verbatim because the only required property is that each ground vertex lies at a boundary between two Gray-code intervals, and the matching $M_0$ connects the two siblings while preserving signature consistency.
Each equivalence class again induces a union of directed cycles in which sibling ground vertices are merged by forcing the $M_0$ edges to remain intact, exactly as in part (c) of Exercise 45.
To obtain a single Hamiltonian cycle, apply the same splicing argument as in Exercise 45(d). Each equivalence class cycle contains all vertices in its class, and the added $M_0$ edges connect these cycles into a single connected 2-regular graph. Since every vertex has degree 2 in the union of selected edges, connectivity implies the structure is a single cycle covering all $2^{kr+2}$ vertices.
The choice of matchings $M_1,\dots,M_k$ corresponds to choosing a partition of the Gray cycle on $k$ bits into $k+1$ labeled transition classes. Each such labeling is determined by a cyclic ordering of coordinate directions compatible with parity constraints. The number of admissible global relabelings is therefore the number of cyclic permutations of $k+1$ symbols respecting the Gray-cycle adjacency, which grows exponentially in $k$ and is on the order of $k!$ up to cyclic symmetry.
Thus the extension preserves the mechanism of Exercise 45: signatures induce a Gray walk on $k$ bits, matchings realize coordinate flips, and equivalence-class merging produces Hamiltonian cycles.
This completes the extension of Exercise 45 to the $(kr+2)$-cube for even $k$. ∎