TAOCP 7.2.1.1 Exercise 83
Represent each domino ${i,j}$, $0 \le i \le j \le 6$, as an undirected edge between vertices $i$ and $j$ in a multigraph $G$ on vertex set ${0,1,\dots,6}$, with one loop at each vertex $i$ correspondi...
Section 7.2.1.1: Generating All n-Tuples
Exercise 83. [41] [41] Can four balanced 8-bit Gray cycles cover all edges of the 8-cube?
316 COMBINATORIAL SEARCHING 7.2.1.1
Verified: no
Solve time: 4m43s
Solution
Represent each domino ${i,j}$, $0 \le i \le j \le 6$, as an undirected edge between vertices $i$ and $j$ in a multigraph $G$ on vertex set ${0,1,\dots,6}$, with one loop at each vertex $i$ corresponding to ${i,i}$. A valid cyclic arrangement of all 28 dominoes is exactly an Euler circuit in $G$, since each domino is used once and consecutive dominoes must share an endpoint.
To apply an Euler-circuit enumeration theorem, replace $G$ by the directed Eulerian multigraph $D$ obtained by replacing each edge ${i,j}$ with two arcs $i \to j$ and $j \to i$ when $i \ne j$, and replacing each loop ${i,i}$ by a single loop arc at $i$. In $D$, each non-loop edge contributes one outgoing arc at each endpoint, and each loop contributes one outgoing and one incoming arc at its vertex.
For each vertex $v$, there are $6$ neighbors $w \ne v$, contributing $6$ outgoing arcs $v \to w$, and one loop contributing one outgoing arc $v \to v$. Hence
$\operatorname{outdeg}(v) = 7,$
and similarly $\operatorname{indeg}(v)=7$, so $D$ is Eulerian.
The BEST theorem gives the number of Euler circuits in a directed Eulerian graph rooted at a fixed starting vertex $r$ as
$$ N_r = \tau_r(D),\prod_{v} (\operatorname{outdeg}(v)-1)!, $$
where $\tau_r(D)$ is the number of directed spanning arborescences oriented toward $r$.
Since every pair of distinct vertices in $D$ is joined in both directions, and loops do not affect arborescences, $\tau_r(D)$ equals the number of arborescences in the complete bidirected graph on $7$ vertices, which is
$$ \tau_r(D) = 7^{7-2} = 7^5. $$
For each vertex,
$$ (\operatorname{outdeg}(v)-1)! = 6!, $$
hence
$$ \prod_v (\operatorname{outdeg}(v)-1)! = (6!)^7. $$
Therefore the number of Euler circuits in $D$ starting at a fixed vertex is
$$ N_r = 7^5 (6!)^7. $$
Each Euler circuit corresponds to a cyclic ordering of the 28 dominoes. A cycle is independent of the starting point and direction. A cycle of length $28$ has exactly $28$ choices of starting edge and $2$ orientations, all yielding the same cyclic arrangement. Hence the number of distinct cycles is
$$ \frac{7^5 (6!)^7}{28 \cdot 2} = \frac{7^5 (6!)^7}{56}. $$
Since $56 = 7 \cdot 8$, this simplifies to
$$ \frac{7^4 (6!)^7}{8}. $$
Thus the number of valid cyclic arrangements is
$$ \boxed{\frac{7^5 (6!)^7}{56}}. $$
∎