Showing that a particular graph is Hamiltonian I am trying to prove the following:
Let $Q:=\{1,2,\cdots q\}$. Let $G$ be a graph with the elements of $Q^n$ as vertices and an edge between $(a_1,a_2,\cdots a_n)$ and $(b_1,b_2,\cdots b_n)$ if and only if $a_i\ne b_i$ for exactly one value of $i$. Show that $G$ is Hamiltonian.
I tried a few cases for n. For n=1 we have a complete graph and for n=2 I found an Hamiltonian circuit 11-13-12-32-22-21-23-33-31-11. However this isnt helping me. Any help please.   
 A: Ok, here's one method that works. (I didn't try to understand the code on Wikipedia. :-))
As said in the comment, the graph $G$ with $\{1,\dots,q\}^n$ as vertices and an edge between strings that differ in exactly one place is known as the Hamming graph $H(n,q)$. A Hamiltonian path/cycle in such a graph is called a $(q,n)$-Gray code: it is a sequence of $q^n$ strings in which each pair of successive strings differ in exactly one place. (For a Hamiltonian cycle, you want that the first and last strings also differ in exactly one place.)
The case where $q=2$ is simple and illustrative: one popular Gray code, called the reflected binary code is constructed as follows: for $n=1$, you write down the sequence $(1, 2)$. For $n>1$, write down the sequence for $n-1$, reflect it (write down the elements of the sequence in reverse order), then append $1$ to each elements of the original sequence and $2$ to each element of the reflected sequence. Thus for $n=2$, you take the sequence for $n=1$ (namely $(1, 2)$), reflect it (so $(2, 1)$), etc., to get $(11, 12, 22, 21)$. Let's use the notation that $a\{S\}$ means the sequence of values $ax$ for $x$ in $S$. (Like Unix shell expansion syntax. Hope this isn't confusing.) For $n=3$, you get $(1\{11, 12, 22, 21\}, 2\{21, 22, 12, 11\})$. Etc.
For general $q$, when $q$ is even, exactly the same algorithm works: to get the sequence for $n$, make $q$ copies of the sequence for $n-1$, in which alternate ones are reflected, and append a different first symbol to each. For instance for $q=4$, start with $(1, 2, 3, 4)$ for $n=1$, then for $n=2$ you have $(1\{1,2,3,4\},2\{4,3,2,1\},3\{1,2,3,4\},4\{4,3,2,1\})$, etc. Unfortunately, for odd $q$, you get a Hamiltonian path that is not a Hamiltonian cycle. For $q=3$ for instance, you start with $(1, 2, 3)$ for $n=1$ and for $n=2$ you get $(1\{1,2,3\}, 2\{3,2,1\}, 3\{1, 2, 3\})$ in which the first and last strings $11$ and $33$ are not adjacent.
To fix this, we can use rotation instead of reflection. Given a sequence $S$ of strings, let $r(S)$ denote the sequence in which the first symbol of each string is decreased by $1 \pmod q$. Observe that if a sequence $S$ is a valid Gray code / valid path in the Hamming graph, then so is $r(S)$ — for any two adjacent strings in $S$, if their first symbols are the same then so are the first symbols of their corresponding strings in $r(S)$, and if the first symbols are distinct (and everything else the same), then so are they in $r(S)$. We can define the $(q,n)$-Gray code as follows:


*

*For $n=1$, take $(1, 2, \dots, q)$.

*For $n>1$, let $S$ be a $(q, n-1)$-Gray code. Then take $(1\{S\}, 2\{r(S)\}, \dots, q\{r^{q-1}(S)\})$
To illustrate this for $q=5$:


*

*For $n=1$, take $(1, 2, 3, 4, 5)$.

*For $n=2$, take $(1\{1, 2, 3, 4, 5\}, 2\{5, 1, 2, 3, 4\}, 3\{4, 5, 1, 2, 3\}, 4\{3, 4, 5, 1, 2\}, 5\{2, 3, 4, 5, 1\})$. You have a path from $11$ to $51$, which for convenience I'll denote $11 \to 51$.

*For $n=3$, take $(1 \{ 11 \to 51\}$, $2\{51 \to 41\}$, $3\{41 \to 31\}$, $4\{31 \to 21\}$, $5\{21 \to 11\})$. So you have a path from $111$ to $511$.
To restate the whole thing in graph-theoretic terms: observe that the Hamming graph $H(n,q)$ consists of $q$ copies of $H(n-1,q)$, with additional edges between vertices that correspond to the same vertex in $H(n-1,q)$. Your Hamiltonian cycle is a Hamiltonian path in the first copy, followed by a Hamiltonian path (starting from its neighbour) in the second copy, followed by a Hamiltonian path in the third copy, etc. You just have to arrange things so that you end at a neighbour of where you start.
