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
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?