(Graph Theory) Prove that $H_n$ has a Hamiltonian cycle for $n$ ≥ 2. Where $H_n$ is the graph that has a vertex for each n-digit binary sequence such that 2 vertices are connected if their binary sequences are different in exactly 1 digit.
Attempt: By induction on n we have,
Base case: True for n=2
Induction hypothesis: $H_n$ has a Hamiltonian cycle for $n$ ≥ 2
Induction step: $H_{n+1}$ has $2^{n+1}$ = $2(2^n)$ vertices so by the induction hypothesis, the graph $K_n$ consisting of every other vertex has a Hamiltonian cycle. Since the other half of the vertices not in $K_n$ all have exactly one digit different from those in $K_n$, $H_{n+1}$ must have a Hamiltonian cycle.
But I'm not sure if the hypothesis $K_n$ immediately follows since those vertices don't differ by only 1 digit.

Here's one solution: Your graph $H_n$ is an n-dimensional hypercube.  For the induction step, separate the cube into two "faces" by cutting along one dimension.  Do parallel Hamiltonian cycles on each of the faces; then cut out the last leg of each cycle and sew them together across the dimension you cut, running the second cycle backwards.  Illustrated below is the case n=3.

I'll leave it to you to turn this into combinatorics.
