Hamiltonian cycle

Question

Assume $A_k$ be an undirected graph with $2^k$ vertices, $\forall k > 1$,$ k \in Z^+$. We use k-digit binary bit strings to label the vertices of $A_k$, where the labels of adjacent vertices differ by exactly one digit. Prove that $A_k$ has a Hamiltonian cycle $\forall k > 1$, $k \in Z^+$.

Answer 1

SKETCH: You can prove it by induction on $k$. The base case is trivial. For the induction step, start at vertex

$$\underbrace{00\ldots00}_{k+1}$$

and trace out a Hamiltonian path in the subgraph whose labels end in $0$, stopping one step short of a cycle, shift the last bit to a $1$, trace out the corresponding path in reverse, and shift the last bit back to $0$; if you done it right, you’re back at the starting vertex. E.g., for the ordinary cube you have $000,010,110,100,101,111,011,001,000$.