Problem1I

Problem 1I: Let ${Q:=\{1,2,...,q\}}$. Let ${G}$ be a graph with the elements of ${Q^{n}}$ as vertices and an edge between ${(a_{1},\ldots ,a_{n})}$ and ${(b_{1},\ldots ,b_{n})}$ if and only if ${a_{i}\neq b_{i}}$ for exactly one value of ${i}$ . Show that ${G}$ is Hamiltonian.

Solution: When ${q=1}$, the graph is trivial. Suppose ${q\geq 2}$. When ${n=1}$, the graph is Hamiltionian since it is a complete graph. Assume that the graph is Hamiltonian for ${n=k}$. Suppose a Hamiltonain circuit of the graph with vertices ${Q^{k}}$ is ${v_{1}v_{2}\cdots v_{q^{k}}v_{1}}$. Then if ${q}$ is even, a Hamiltonian circuit for ${n=k+1}$ would be

$\displaystyle (v_{1},1)(v_{2},1)\cdots (v_{q^{k}},1)(v_{q^{k}},2)(v_{q^{k}-1},2)\cdots (v_{1},2)(v_{1},3)(v_{2},3)\cdots (v_{1},q)(v_{1},1).$

If ${q}$ is odd, if use the same procedure, we would obtain

$\displaystyle (v_{1},1)(v_{2},1)\cdots (v_{q^{k}},1)(v_{q^{k}},2)(v_{q^{k-1}},2)\cdots (v_{1},2)(v_{2},3)(v_{q^{k}},3)\cdots (v_{q^{k}},q),$

which cannot be a circuit. So we use a different procedure, keep the first ${ q^{k}(q-2)}$ points same as before, and the last ${2q^{k}+1}$ points are:

$\displaystyle (v_{q^{k}},q-1)(v_{q^{k}},q)(v_{q^{k}-1},q)(v_{q^{k}-1},q-1)(v_{q^{k}-2},q-1)\cdots (v_{1},q-1)(v_{1},q)(v_{1},1).$

This is a Hamiltonian circuit for odd ${q.}$ The induction completes.

Notes: If ${q}$ is ${\geq 5}$, we can find another way to produce Hamiltonian circuit by exchanging the points in the circuit of even ${q}$ case: W.L.O.G., assume there is a path segment ${ v_{q^{k}-1}v_{q^{k}}v_{1}v_{2}v_{3}}$ from the Hamiltonian circuit of ${Q^{k}}$ , and these ${5}$ points differ on the same position. Hence exchanging ${ v_{1},v_{2}}$ or exchanging ${v_{2},v_{q^{k}}}$ would not destroy the Hamiltonian circuit. Now exchange ${(v_{1},1)}$ , ${(v_{2},1)}$, and exchange ${ (v_{2},q)}$, ${(v_{q^{k}},q)}$, then a Hamiltonian circuit forms.

Find a Hamiltonian circuit is not easy. In general case, it is NP hard. However, if the graph has a ‘nice’ representation, it might be easy to find one.