Prove, by induction on
, that every hypercube graph
,
, contains a Hamiltonian cycle.
(Hint: Assume inductively that graph
contains a Hamiltonian path from node
to node
. Observe that
two such paths can be connected into a similar
Hamiltonian path in
.) Draw pictures of the
Hamiltonian paths based on this construction for
the graphs
and
.
(Note: The Hamiltonian cycles of hypercube
correspond to so called cyclic Gray codes of the integers
0, ...,
. These have the property
that the binary representations of any two consequent
numbers differ in exactly one bit.)