TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 29

Show that the n-dimensional hypercube is Hamiltonian for $n\ge 2$.

Solution

Proof: By induction on n. In the base case n = 2, the 2-dimensional hypercube, the length four cycle starts from 00, goes through 01, 11, and 10, and returns to 00.

Suppose now that every (n-1)-dimensional hypercube has an Hamiltonian cycle. Let $v\in \{0,1{\}}^{n-1}$ be a vertex adjacent to $0^{n-1}$ (the notation $0^{n-1}$ means a sequence of n - 1 zeroes) in the Hamiltonian cycle in a (n−1)-dimensional hypercube. The following is a Hamiltonian cycle in an n-dimensional hypercube: have a path that goes from $0^n$ to $0v$ by passing through all vertices of the form $0x$ (this is simply a copy of the Hamiltonian path in dimension (n − 1), minus the edge from $v$ to $0^{n-1}$), then an edge from $0v$ to $1v$, then a path from $1v$ to $10^{n-1}$ that passes through all vertices of the form $1x$, and finally an edge from $10^{n-1}$ to $0^n$.

This completes the proof of the Theorem.

When we start from $0^n$ and we follow the Hamiltonian tour described in the above proof, we find an ordering of all the n-bit binary strings such that each string in the sequence differs from the previous string in only one bit. Such an ordering is called a Gray code (from the name of the inventor) and it has various application.

Source: https://web.archive.org/web/*/http://inst.eecs.berkeley.edu/~cs70/sp07/lec/lecture14.pdf or https://inst.eecs.berkeley.edu/~cs70/sp07/lec/lecture14.pdf