# 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 ...$ |