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.


1 Answer 1


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.

enter image description here

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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .