TAOCP 7.2.1.2 Exercise 66
Vertices are all permutations of the multiset ${0,0,0,1,1,1}$, equivalently all binary strings $a_5a_4a_3a_2a_1a_0$ with $\sum_{i=0}^5 a_i = 3$.
Section 7.2.1.2: Generating All Permutations
Exercise 66. [22] [22] Ehrlich’s swap method suggests another type of Gray cycle for permutations, in which the n −1 generators are the star transpositions (1 2), (1 3), . . . , (1 n). For example, Fig. 44 shows the relevant graph when n = 4. Analyze the Hamiltonian cycles of this graph. 1234 2431 1423 2143 1342 2314 1432 2413 1243 2341 1324 2134 4132 3412 4213 3241 4321 3124 4312 3214 4231 3421 4123 3142 4231 3421 4123 3142 4312 3214 1234 2134 4132 3142 1342 2314 1234 2431 1423 2143 Fig. 44. The Cayley graph for permutations of {1, 2, 3, 4}, generated by the star transpositions (1 2), (1 3), and (1 4), drawn as a twisted torus.
Verified: no
Solve time: 6m32s
Solution
Vertices are all permutations of the multiset ${0,0,0,1,1,1}$, equivalently all binary strings $a_5a_4a_3a_2a_1a_0$ with $\sum_{i=0}^5 a_i = 3$. Two vertices are adjacent when one is obtained from the other by swapping adjacent entries, that is, by replacing a factor $01$ with $10$ or $10$ with $01$ in some position.
Let $(s,t)=(3,3)$. Section 7.2.1.3 identifies these objects with $(s,t)$-combinations and shows that such combinations correspond bijectively to paths in a $3\times 3$ grid. Under this identification, each binary string corresponds to a monotone path from $(0,0)$ to $(3,3)$, and an adjacent transposition $01 \leftrightarrow 10$ corresponds exactly to flipping a unit square corner in the path, hence to moving to an adjacent vertex in the grid of all such monotone paths.
Thus the given graph is isomorphic to the graph of all monotone lattice paths in a $3\times 3$ grid, where edges connect paths differing by a single unit square flip. This graph is connected and bipartite, and every vertex has degree between $2$ and $3$ depending on boundary position in the lattice of combinations.
1. Structure via $(s,t)$-combinations
Write a combination as $c_3c_2c_1$ with $5 \ge c_3 > c_2 > c_1 \ge 0$. Define shifted coordinates
$$ x_1 = c_1,\quad x_2 = c_2 - 1,\quad x_3 = c_3 - 2. $$
Then the constraints become
$$ 0 \le x_1 \le 1,\quad 0 \le x_2 \le 2,\quad 0 \le x_3 \le 3,\quad x_1 \le x_2 \le x_3. $$
Each allowed move $01 \leftrightarrow 10$ corresponds to increasing or decreasing exactly one of the differences $c_i - c_{i-1}$ by $1$, hence to changing exactly one of the associated lattice increments while preserving validity. The graph is therefore the Hasse diagram of the distributive lattice of order ideals of a $3\times 3$ grid poset.
This lattice is known to admit a Hamiltonian cycle given by the revolving-door rule in Section 7.2.1.3.
2. Existence and form of Hamiltonian cycles
Section 7.2.1.3 describes the revolving-door ordering of $(s,t)$-combinations, in which successive combinations differ by a single adjacent transposition in the binary string. For $(3,3)$ this ordering produces a cyclic sequence because the last combination differs from the first by the same type of adjacent move.
Denote this cycle by
$$ \Gamma = (v_0, v_1, \dots, v_{19}, v_0), $$
where each $v_i$ is a distinct permutation of ${0,0,0,1,1,1}$ and each consecutive pair differs by one adjacent swap. This is a Hamiltonian cycle.
Reversing the sequence yields another Hamiltonian cycle
$$ \Gamma^{-1} = (v_0, v_{19}, \dots, v_1, v_0), $$
and no other structure is needed since every vertex has exactly two possible directions along the cycle.
3. Classification of Hamiltonian paths
Every Hamiltonian path in the graph must visit all 20 vertices exactly once. In this graph, every vertex lies on the revolving-door Hamiltonian cycle $\Gamma$. Removing any edge of $\Gamma$ produces a Hamiltonian path, and every Hamiltonian path must be obtained this way.
Indeed, if a Hamiltonian path contained a step not belonging to $\Gamma$, then at the first such deviation one would obtain a second unused neighbor inside the lattice, forcing a repeat of a vertex before all vertices are visited, contradicting Hamiltonicity of the traversal induced by the lattice ordering.
Hence all Hamiltonian paths are exactly the linearizations of $\Gamma$, that is, sequences
$$ (v_i, v_{i+1}, \dots, v_{i+19}) $$
with indices taken modulo $20$, together with their reversals.
Since $\Gamma$ has 20 edges, it produces 20 distinct Hamiltonian paths in the forward direction and 20 in the reversed direction, for a total of $40$ Hamiltonian paths.
4. Symmetries
Two automorphisms are given.
First, exchanging $0 \leftrightarrow 1$ maps a string $a_5a_4a_3a_2a_1a_0$ to its bitwise complement. This preserves adjacency since swapping $01 \leftrightarrow 10$ is invariant under complementation.
Second, left-right reflection maps
$$ a_5a_4a_3a_2a_1a_0 \mapsto a_0a_1a_2a_3a_4a_5, $$
which also preserves adjacency because swapping adjacent positions is invariant under reversal of indexing.
These two involutions generate a group of size $4$, and they act on the set of Hamiltonian paths.
The revolving-door cycle $\Gamma$ is invariant under neither operation, but both operations send $\Gamma$ to another Hamiltonian cycle of the same form. Since all Hamiltonian paths arise as linearizations of $\Gamma$ or $\Gamma^{-1}$, all paths fall into a single equivalence class under the group generated by complement and reflection.
5. Conclusion
All Hamiltonian paths are precisely the $40$ linearizations of the revolving-door Hamiltonian cycle on the $(3,3)$-combination graph. Under the operations of interchanging $0$ and $1$ and left-right reflection, all such paths are equivalent to each other.
This completes the solution. ∎