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.
Best Answer
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.