4
$\begingroup$

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.

$\endgroup$

1 Answer 1

15
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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