Traversing the Hypercube

Ossarion-429 is a multi-dimensional being travelling across hypercubes of various dimensions. Bored and having nothing else to do, he wonders to himself if it’s possible to travel along the edges of a hypercube, visiting each vertex exactly once before returning to the start. Such a path is called a Hamiltonian cycle.

Excited with the challenge, he takes a look at a 2D hypercube, an object that you would call a “square”. Starting at a vertex, he easily finds that he can traverse the following path, visiting each vertex exactly once.

Up next is a 3D hypercube, or a “cube”. With more options at each vertex to navigate, it’s harder to find a route that traverses each vertex only once. Eventually, though, Ossarion-429 finds such a path. Can you find it too?

So far so good; we’ve managed to find a Hamiltonian cycle for 2D and 3D hypercubes. But how about a 4-dimensional hypercube? Or 5? As the number of vertices increases exponentially with the number of dimensions, would there ever be a hypercube that doesn’t have a Hamiltonian cycle? If yes, what’s the smallest n such that an n-dimensional hypercube has no such path? If not, prove it.

Solution

All n-dimensional hypercubes have a Hamiltonian cycle, so long as $n \geq 2$ , which I’ll explain why at the end.

Let’s prove this by considering the Hamiltonian cycle on a square.

To construct a cube, we can place 2 squares side by side and connect their corresponding vertices.

Let’s draw a Hamiltonian cycle for each square, leaving out the last edge that brings us back to the start. We’ll also reverse the path on one of the squares.

Note how we can connect the two paths together like this, forming a Hamiltonian cycle for a cube.

We can perform a similar process to construct a Hamiltonian cycle for a 4D hypercube.

This works for higher-dimensional hypercubes, proving that there will always be a Hamiltonian cycle.

Extra Credit

There’s also another way to solve this. Let’s consider a cube with unit length, placing one corner at the origin of a 3D cartesian space. Its vertices will be at the coordinates (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), and (1, 1, 1). We then convert each vertex directly into binary by concatenating its coordinates. For instance, the vertex at (1, 0, 1) will be 101. If you know what Gray codes are, you’ll notice that the Gray code sequence of length 3 will form our Hamiltonian cycle.

000, 001, 011, 010, 110, 111, 101, 100.

This works because of 3 facts:

Every number in the Gray code sequence is unique, ensuring that we will never visit the same vertex twice.
2 vertices are connected by an edge if and only if their coordinates differ by 1 value. For instance, (0, 0, 0) is adjacent to (1, 0, 0), (0, 1, 0), and (0, 0, 1). Since each consecutive number in the Gray code differs by at most one value, the sequence forms a valid path on the cube.
The last number in the Gray code sequence is only 1 bit off from the first number, allowing us to form a closed cycle.

Let’s take a look at our earlier examples with the binary labels.

But why is this not true for $n = 1$ ? Well, that’s because a 1D hypercube is just a line.

The path that traverses each vertex once will start at one vertex, go to the other, then back, crossing the same edge twice. In graph theory, cycles cannot repeat a vertex or an edge, so we cannot consider this a Hamiltonian cycle based on this technicality.

Try These Next

Jewel Thieves and a Stolen Gem

Stack of Coins 1B

Vanishing Square