0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.