How can it be proven that gray code is the only possible way to arrange points in a 2^n graph with consecutive points only seperated by 1 bit?

I think that the title already explains everything; I have been unable to prove that gray code is, for any dimension n for which n is a natural number, the only way to order all of the 2^n points in a 2^n grid so that consecutive points are separated only by one bit (including the starting and ending point). If anything requires clarification, I would be happy to do so.

It should be mentioned that the different iterations of Gray Code are identical in the context of my question as they are simply "rotations" of the n-dimensional structure which is created when linking together the points written out as 0's and 1's.
For example, if n=3, the corresponding Gray code may be 000 001 011 010 110 111 101 100 or 000 100 110 010 011 111 101 001, both of these are rotations of the same structure (namely the first iteration of the 3-dimensional Hilbert curve skullsinthestars.files.wordpress.com/2014/03/hilbertcurve3d.‌​jpg) in three-dimensional space.

• Bad news: there are many gray codes; your description defines gray codes. – Dan Uznanski May 22 '17 at 17:15
• What exactly do you mean by "gray code"? There are many ways to organize a gray code. For example, for 3-bit strings, you can choose any of the 3 positions to vary first, and any of the two remaining ones to vary second. If you imagine the code as a path through an $n$-cube, these correspond do rotations or reflections of the cube. – MJD May 22 '17 at 17:15
• Thank you for your answer. Unfortunately, the different iterations of Gray Code are identical in the context of my question as they are simply "rotations" of the n-dimensional structure which is created when linking together the points written out as 0's and 1's. – J. A May 23 '17 at 12:46
• For example, if n=3, the corresponding Gray code may be 000 001 011 010 110 111 101 100 or 000 100 110 010 011 111 101 001, both of these are rotations of the same structure (namely the first iteration of the 3-dimensional Hilbert curve skullsinthestars.files.wordpress.com/2014/03/hilbertcurve3d.jpg) in three-dimensional space. Perhaps more accurate terminology would be to say that these structures always have to be similar. – J. A May 23 '17 at 12:46
• I apologise if my explanations are confusing, I am not as versed in Gray Code as I would like to be. – J. A May 23 '17 at 12:49

1 Answer

There are many Gray codes.

For three bits, there are $12$: you get a choice of which of three bits you wish to turn on first, then which of two bits you wish to turn on second, and finally whether you wish to turn on the third bit or turn off the first next.

These however are all isomorphic to each other: by permuting what order the bits are selected, or by choosing a different starting point, all of these cycles can be transformed into one another.

But this isn't true for four bits!

With four bits, there are $11$ distinct gray codes, listed below.

 (0, 1, 3, 2, 6, 4, 5, 7, 15, 11, 9, 13, 12, 14, 10, 8) (0, 1, 3, 2, 6, 4, 5, 7, 15, 11, 10, 14, 12, 13, 9, 8) (0, 1, 3, 2, 6, 4, 5, 7, 15, 13, 12, 14, 10, 11, 9, 8) (0, 1, 3, 2, 6, 4, 5, 7, 15, 14, 10, 11, 9, 13, 12, 8) (0, 1, 3, 2, 6, 4, 5, 7, 15, 14, 12, 13, 9, 11, 10, 8) (0, 1, 3, 2, 6, 4, 12, 13, 5, 7, 15, 14, 10, 11, 9, 8) (0, 1, 3, 2, 6, 4, 12, 14, 10, 11, 15, 7, 5, 13, 9, 8) (0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 9, 11, 15, 14, 10, 8) (0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8) (0, 1, 3, 2, 6, 7, 5, 13, 9, 8, 10, 11, 15, 14, 12, 4) (0, 1, 3, 2, 6, 7, 5, 13, 15, 14, 10, 11, 9, 8, 12, 4)

I'm uncertain how many there are in five bits; what I've seen suggests that the number reaches into the hundreds of thousands.

• Do you have a reference for the 11? I looked in OEIS and couldn't find anything exactly like that. The closest I could come was Number of Hamiltonian cycles in the n-hypercube up to automorphism which begins $1,1,1,9$. – MJD May 23 '17 at 14:35
• That is strange. Hang on while I fiddle my script, I had an idea. – Dan Uznanski May 24 '17 at 8:40
• Idea came through. Okay. The difference is apparently that two pairs of my codes -- #1 and #4, and also #6 and #8 -- are available as reverses of one another. I had tested shifts of starting point, and permutations of bits, but reversing the codes hadn't occurred to me earlier. – Dan Uznanski May 24 '17 at 8:48