$!!$ Exercise $10\mathrm{.}1\mathrm{.}4$: Consider the graphs whose nodes are grid points in an $n-$

dimensional cube of side $m,$ that is$,$ the nodes are vectors $(i_1,i_2,$dots,$i_n),$ where

each $i_j$ is in the range $1$ to $m.$ There is an edge between two nodes if and only

if they differ by one in exactly one dimension. For instance, the case $n=2$ and

$m=2$ is a square, $n=3$ and $m=2$ is a cube, and $n=2$ and $m=3$ is the graph

shown in Fig. $10\mathrm{.}3.$ Some of these graphs have a Hamilton circuit, and some do

not. For instance, the square obviously does, and the cube does too, although it

$m$ ay not be obvious; one is $(0,0,0),(0,0,1),(0,1,1),(0,1,0),(1,1,0),(1,1,1),$

$(1,0,1),(1,0,0),$ and back to $(0,0,0).$ Figure $10\mathrm{.}3$ has no Hamilton circuit.

a$)$ Prove that Fig. $10\mathrm{.}3$ has no Hamilton circuit. Hint: Consider what hap$-$

pens when a hypothetical Hamilton circuit passes through the central

node. Where can it come from, and where can it go to$,$ without cutting

off one piece of the graph from the Hamilton circuit?

b$)$ For what values of $n$ and $m$ is there a Hamilton circuit?