Hamiltonian Cycle in a Graph with Vertices with Binary Labels 
Let $A_k$ be an undirected graph with $2^k$ vertices for $k > 1$, $k \in \mathbb{Z}^+$. We use $k$-digit binary strings to label the vertices of $A_k$, where two vertices are adjacent if and only if their binary labels differ by exactly one digit. Prove that $A_k$ has a Hamiltonian cycle $\forall k > 1, k \in Z^+$.

How can I prove this claim? This looks too complex for me.
 A: Because $k \in \mathbb{Z}^+$, this claim is screaming to be proven inductively. For our basis of induction, if we look at the case where $k=2$, the graph $A_k$ is just a square on $4$ vertices. A Hamiltonian cycle in this graph is pretty easily discovered.
Before tackling the inductive step, let's introduce some notation. Suppose we have a vertex $v$ in $A_k$. If I want to talk about the vertex in $A_{k+1}$ with the same $k$-digit binary label as $v$ but with a $0$ prefixed to it, I'll write $0v$. For example if we have $v = 0101$ in $A_4$, we can talk about two vertices in $A_5$ that look like $1v = 10101$ and $0v = 00101$.
Now for our inductive step suppose that for some $k>1, k \in \mathbb{Z}^+$ we have that $A_k$ has a Hamiltonian cycle. What must $A_{k+1}$ look like? For each vertex $v$ in $A_k$, we have exactly two corresponding vertices in $A_{k+1}$, namely $0v$ and $1v$. But then what are the edges of $A_{k+1}$? Note the following facts:


*

*The vertices $0v$ and $0w$ (respectively $1v$ and $1w$) are adjacent in $A_{k+1}$ if and only if the vertices $v$ and $w$ are adjacent in $A_k$.

*The vertices $0v$ and $1w$ are adjacent in $A_{k+1}$ if and only if $v = w$.
With this in mind, $A_{k+1}$ must look like two copies of $A_k$ (one with $0$ prefixed to the binary string of each vertex and the other with $1$ prefixed to the binary string of each vertex) with additional edges placed between vertices $0v$ and $1v$ for each vertex $v$ of $A_k$.
So then the question becomes, "how do we extend the Hamiltonian cycle in $A_k$ to a Hamiltonian cycle in $A_{k+1}$?" If we suppose we have a edge of the Hamiltonian cycle of $A_k$ between vertices $x$ and $y$, we can substitute that edge for the path $\{0x, 1x, 1y, 0y\}$ in $A_{k+1}$ (noting that these edges must exists by our bullet points above). Doing this substitution over all the edge of the Hamiltonian cycle of $A_k$ will yield a Hamiltonian cycle in $A_{k+1}$.
