Finding a Hamiltonian cycle for the set of RGB colors?

Question

I'm consulting on an art project where a question about colors came up.

Consider the RGB colors as a graph.

• The nodes are ordered triples $(r, g, b)$ where each entry is an integer from $[0, 255]$.
• The distance between two nodes $(r, g, b)$ and $(r', g', b')$ is defined to be $|r - r'| + |g - g'| + |b - b'|$.
• There is an edge between two nodes if and only if the distance between them is $1$.

It's easy to find a Hamiltonian path for this graph - for a sketch I used the Grey code algorithm presented in Guan 1998 - but this starts on black $(0, 0, 0)$ and ends on white $(255, 255, 255)$ so it is emphatically not a cycle.

For what it's worth, there are $8$ nodes of order $3$ and many ($387096 = 2 \cdot 3 \cdot 254 \cdot 254$) nodes of order $5$ (any triple containing exactly one of $0$ or $255$), so no Eulerian path is possible.

And it's easy to construct an Hamiltonian cycle using a variation on Guan for $4$-tuples - but unfortunately, color models only have three components.

Experimentation leads me to believe that such a cycle does not exist for $3$-tuples - if you try to work in two directions from black, you can make progress, but it seems you leave behind nodes that you won't ever be able to reach again - and my intuition is that some sort of parity argument should be possible, but an actual proof has eluded me.

Best result would be a construction of a Hamiltonian cycle for this graph. Almost as good would be a maximal Hamiltonian subcycle. An existence or nonexistence proof would be super too!

Answer 1

Such a cycle is possible, and I'll try to explain it to you:

First node in the graph will be (0,0,1), then we will go (0,0,2),(0,0,3),...,(0,0,255). Now we move to the next line and go (0,1,255),(0,1,254),(0,1,253),...,(0,1,1),(0,1,0). Next line - (0,2,0),(0,2,1),...,(0,2,255) and so on, on the last line we will go (0,255,255),(0,255,254),...,(0,255,0). Now we move one "plane" up, and backtrack - we go (1,255,0),(1,255,1),...,(1,255,255),(1,254,255),(1,254,254),...,(1,254,0),(1,253,0),... ..., (1,0,2),(1,0,1), and now we go one plane higher again, to (2,0,1) and we repeat what we did in 0-th plane, and in third plane we repeat what we did in first plane etc.

In the end, we will be at (255,0,1). Now we finish the cycle - we go (255,0,0),(254,0,0),(253,0,0),...,(1,0,0),(0,0,0).

I hope I was clear enough, if you have any more questions, ask in a comment.

Answer 2

If you look at your vertices like lattice points you get something like this:

The subgraph $H$ which only contains the edges shown in the picture is a subgraph of the one you have. This graph is hamiltonian.

Proof: Consider only the top layer, call that graph $K$. That layer is hamiltonian whenever the number of points in the layer is even. $H$ is isomorphic to $K\square P_{256}$. And the cartesian product of a hamiltonian graph and a graph with a hamiltonian path is always hamiltonian.