Gray Codes

Definition: A Gray Code for $k$-bit words is an ordered list of $2^k$ many $k$-bit binary words (containing $0$'s and/or $1$'s) in which consecutive binary words differ by exactly one bit.

Recall Hamiltonian Graphs and Cube Graphs. The definition of a Cube graph is a graph $G = (V(G), E(G))$ is a graph that is obtained by taking all vertices denoted as binary words and joining the vertices with the edge whenever the binary words differ by $1$. While the definition of a Hamiltonian Graph is a graph $G = (V(G), E(G))$ is considered Hamiltonian if and only if the graph has a cycle containing all of the vertices of the graph

One property of cube graphs is that they are in fact Hamiltonian, and since each vertex in a cube graph is only joined to vertices with an edge whenever binary words differ by $1$ means that if we find what is known as a Hamiltonian Path for these $Q_k$ graphs, then we have successfully determined a gray code.

Let's recall $Q_1$, $Q_2$, and $Q_3$:

$Q_1$ has a rather obvious Hamiltonian path as seen in blue:

So a possible gray code for $Q_1$ is $0 1$

$Q_2$ also has a rather obvious Hamiltonian path, once again highlighted in blue:

So a possible gray code for $Q_2$ is $00 01 11 10$

Now let's look at the more complex graph, $Q_3$. Here is a potential Hamiltonian path for $Q_3$ containing all vertices in $Q_k$:

Hence we can obtain the gray code of $000 010 110 100 101 111 011 001$

Of course, drawing our graphs such as $Q_4$ and $Q_5$, …, will become ever more tedious. Here are some gray codes up to $Q_5$:

Number of Bits	Gray Code
$1$-bit ($Q_1$)	$0 1$
$2$-bit ($Q_2$)	$00 01 11 10$
$3$-bit ($Q_3$)	$000 001 011 010 101 111 110 100$
$4$-bit ($Q_4$)	$0000 0001 0011 0010 0101 0111 0110 0100 1001 1011 1111 1101 1010 1110 1100 1000$
$5$-bit ($Q_5$)	$00000 00001 00011 00010 00101 00111 00110 00100 01001 01011 01111 01101 01010 01110 01100 01000 ...$