TAOCP 7.2.1.3 Exercise 108
Let $G$ be the multigraph whose vertices are ${0,1,2,3,4,5,6}$ and whose edges are the $28$ dominoes of the double-six set, namely one edge between $i$ and $j$ for each $0 \le i \le j \le 6$, includin...
Section 7.2.1.3: Generating All Combinations
Exercise 108. [M31] [M31] Find universal cycles of 3-combinations for the sets {0, . . . , n −1} when n mod 3 ̸= 0.
Verified: no
Solve time: 4m02s
Solution
Let $G$ be the multigraph whose vertices are ${0,1,2,3,4,5,6}$ and whose edges are the $28$ dominoes of the double-six set, namely one edge between $i$ and $j$ for each $0 \le i \le j \le 6$, including one loop at each vertex.
A valid cycle of dominoes is a cyclic ordering of all edges such that consecutive dominoes share a common endpoint. This is exactly an Euler circuit of $G$, since each edge is used once and adjacency forces continuity at vertices, including the last edge connecting back to the first.
The graph is connected and Eulerian because each vertex $v$ has degree
$$ \deg(v) = 6 + 2 = 8, $$
since it is adjacent to the other $6$ vertices and has one loop contributing $2$ to the degree. Hence $\deg(v)$ is even for all $v$, so Euler circuits exist.
To count Euler circuits, we apply the standard formula for undirected Eulerian multigraphs obtained from the BEST theorem applied to the directed line graph formulation. For a connected Eulerian multigraph $G$, the number of Euler circuits is
$$ \tau(G),\prod_{v \in V} \left(\frac{\deg(v)}{2} - 1\right)!,2^{|E| - |V| + 1}, $$
where $\tau(G)$ is the number of spanning trees of the underlying simple graph (loops do not affect spanning trees).
The underlying simple graph is $K_7$, so by Cayley’s formula,
$$ \tau(G) = 7^{7-2} = 7^5. $$
For each vertex,
$$ \frac{\deg(v)}{2} - 1 = \frac{8}{2} - 1 = 3, $$
so each factor is $3! = 6$. With seven vertices,
$$ \prod_{v \in V} \left(\frac{\deg(v)}{2} - 1\right)! = 6^7. $$
The graph has $|E| = 28$ edges and $|V| = 7$ vertices, so
$$ 2^{|E| - |V| + 1} = 2^{28 - 7 + 1} = 2^{22}. $$
Multiplying these contributions gives the number of Euler circuits:
$$ 7^5 \cdot 6^7 \cdot 2^{22}. $$
Hence the number of domino cycles is
$$ \boxed{7^5 \cdot 6^7 \cdot 2^{22}}. $$
This completes the solution. ∎