# Hamiltonian circuit in a Hamming graph

The problem is exactly what I have asked here:

Showing that a particular graph is Hamiltonian

Let $Q:=\{1,2,\ldots, q\}$. Let $G$ be a graph with the elements of $Q^n$ as vertices and an edge between $(a_1,a_2,\ldots, a_n)$ and $(b_1,b_2,\ldots, b_n)$ if and only if $a_i\ne b_i$ for exactly one value of $i$. Show that $G$ is Hamiltonian.

My question is whether my partial solution (given below) is correct and to complete the solution on similar lines?

We induct on $n$. For $n=1$, the graph $K_q$ is clearly Hamiltonian. Assume that for $n-1$ the corresponding graph on $Q^{n-1}$ vertices has a Hamiltonian circuit $x_1,x_2,\ldots,x_{q^{n-1}},x_1$. Now consider the graph $G$ and consider the case when $q$ is even.

The Hamiltonian circuit is: $$1x_1,2x_1,\ldots,qx_1,qx_2,(q-1)x_2,\ldots,1x_2,1x_3,2x_3,\ldots,1x_{q^{n-1}},1x_1.$$

Edit: I could not follow Henning Makholm's hint given below, but the following solution struck me as more simple. Is it correct?

We induct on $n$. For $n=1$, the graph $K_q$ is clearly Hamiltonian. Assume that for $n-1$ the corresponding graph on $Q^{n-1}$ vertices has a Hamiltonian circuit $x_1,x_2,\ldots,x_{q^{n-1}},x_1$. Now consider the following Hamiltonian circuit to complete the proof:

$$1x_1,1x_2,\ldots,1x_{q^{n-1}-1},2x_{q^{n-1}-1},x_{q^{n-1}-2},\ldots,2x_1,3x_1,\ldots,y,qx_{q^{n-1}},(q-1)x_{q^{n-1}},\ldots,1x_{q^{n-1}},1x_1$$ where $y=qx_1$ or $y=qx_{q^{n-1}-1}$ depending on whether $q$ is even or odd respectively.

Yes, that looks like it will work.

In order to remove the dependency on $q$ being even, you can modify your solution such that next-to-last layer ends at an index between $1$ and $q-1$, which will allow the last layer to end at index $1$ no matter whether it's odd or even.

(This requires $q\ge 3$, but $q=2$ can be handled by your existing solution for even $q$).