Applying the odd-m Hamiltonian cycle construction to even m (m=2 and m=4).
Does the decomposition still work? Spoiler: it doesn't — but let's see how it breaks.
Recall: Claude's construction produces 3 directed Hamiltonian cycles that
partition all 3m³ arcs of the m-ary 3-cube digraph — but only for odd m > 1.
Below we apply the same rules to even m to see what goes wrong.
Interactive 3D Visualizations
Drag to rotate. Scroll to zoom. Click a vertex to see its 3 outgoing arcs.
m = 2: 8 vertices, 24 arcs
m = 4: 64 vertices, 192 arcs
Why does the m=2 visualization appear to show only 12 arcs instead of 24?
For m=2, bumping a coordinate means flipping a bit: (x+1) mod 2 = 1−x. So bumping i
on (0,j,k) goes to (1,j,k), and bumping i on (1,j,k) goes right back to (0,j,k).
Every arc has a matching reverse arc along the same edge — the two directed
arrows overlap visually as a single line. The 3-cube has 12 undirected edges, each carrying
2 directed arcs (one in each direction), giving 24 total arcs that appear as 12 overlapping pairs.
This is unique to m=2. For m ≥ 3, bumping i on (1,j,k) goes to (2,j,k) —
a different vertex — so arcs don't double back. This reversibility is also
why the Hamiltonian cycle decomposition fails for m=2: when every arc is immediately reversible,
you cannot form a directed Hamiltonian cycle that visits all 8 vertices without retracing an edge.
Do Hamiltonian Cycles Exist for Even m?
Yes — Hamiltonian cycles exist for all m ≥ 2.
The digraph is strongly connected and 3-regular (every vertex has in-degree = out-degree = 3),
which makes Hamiltonian cycles very likely. Here is one for m=2:
All 8 vertices visited exactly once, using 8 of the 24 arcs.
What's special about odd m is not the existence of cycles, but the
perfect decomposition: all 3m³ arcs can be partitioned into exactly
3 edge-disjoint Hamiltonian cycles, with every arc belonging to exactly one cycle.
That's Claude's theorem.
For even m, this decomposition fails. The key obstacle is the 2-cycle structure shown above:
for even m, bumping the same coordinate twice returns to the original vertex
(since 2 divides m), creating back-and-forth arc pairs. These paired arcs create parity
constraints that prevent a clean 3-way partition. For odd m, bumping any coordinate twice
always moves to a new vertex, giving the digraph the asymmetry the decomposition requires.