Prove by induction any $k$-hypercube (for$ k>1$) has a Hamilton Circuit I have a basic understanding of graph theory and I know what a Hamiltonian circuit is, but I really need help with this proof, it makes little since to me. Thanks so much in advance for the help!! 
Here is the question: 
Recall the construction of a $k$-dimensional hypercube as a graph. Prove by induction any $k$-hypercude (for $k>1$) has a Hamiltonian circuit.
Hint for induction step: 
Define h2 as a Hamiltonian circuit in the 2 dimensional hypercube. How can you build a Hamiltonian circuit on the 3-hypercube using h2? Take your idea and generalize it to build a Hamiltonian circuit for the k-hypercube given hk-1
 A: As some starting help, consider the case of moving from a square to a cube (the smallest dimension case for which this holds).
A cube can be seen as two copies of a square, with edges joining the two copies across all the matched vertices. 
Then by the induction hypothesis, a Hamiltonian circuit exists on each of the squares. Can you see how to link up those two circuits to make a circuit for the cube?
A: Another way of using Induction for this problem is as follows. I'll denote the $n+1-$Hypercube by $Q_n$.
We know that $Q_{n+1}$ = $Q_n \square  K_2$. Where $ \square  $ denotes the Cartesian Product of two graphs.
Base : for $n=2$, we know that $Q_{2}$ is Hamiltonian.
Induction : Suppose that the $Q_{n}$ is Hamiltonian. 
Also we know that $K_2$ is Hamiltonian. 
It's already known that if $G$ and $H$ are Hamiltonian then $G \square  H$ is also Hamiltonian. 
Therefore it follows that $Q_{n+1}$ = $Q_n \square  K_2$ is Hamiltonian.
Hence it follows that, for all $n \geq 2$, the $Q_n$ is Hamiltonian.
