Show that $G$ has a Hamiltonian cycle

Question

Let $X$ be a finitely set, $|X|=n\geq 2$, and $V=P (X) $, define the graph $ G = (V, E) $ by: $$ \{S,T\}\in E \Leftrightarrow |S\Delta T|=1 $$ note that this graph is bipartite.

Show that $ G $ has a Hamiltonian cycle.

My idea is to prove by recurrence on $ n $.

for $ n = 2 $: we pose $ X = \{a, b \} $, we have: $ V = \{\emptyset , \{a \}, \{b \}, \{a, b \} \} $, we see that:

$$ E =\{\{\emptyset , \{a\} \} ; \{\{a\} , \{a,b\}\} ; \{\{a,b\}, \{b\}\} ; \{\emptyset ,\{b\}\} $$

so $ G $ has a Hamiltonian cycle.

But, I can't generalize for all $ n $, an idea please.

Answer 1

As mentioned in the comments you can identify subsets of a finite set $\{x_1...x_n\}$ with bitstrings (i.e. words consisting of the letters 0 and 1) of length $n$. These itself correspond to vertices of an $n$-dimensional hypercube. Moreover the condition on the edges of your graph $G$ precisely means that the edges are the edges of the hypercube.

Now, what is left to show is that any $n$dimensional hypercube graph admits a hamiltonian cycle. For simplicity we will show that it admits a hamiltonian path. It is easy to see for $n=1,2$ that the cube admits a hamiltonian path. Inductively we can define a hamiltonian path, by going the one for dimension $n-1$ through the vertices with $n$th component 0, then going the dimension up to the vertices with $n$th component 1 and going the hamiltonian path of dimension $n-1$ to all those vertices in reversed direction.

Answer 2

I'll prove this by induction on the size of the set $X$.
You proved the base case already, so I'll prove the step.

---

Step

Let $X$ be some set where $\vert X\vert = n$, and let $C$ be a Hamilton cycle in $G$ (of length $2^n$).

Denote $X'=X\cup \{a\}$ where $a\notin X$.

I'll show how to construct a new Hamilton cycle, $C'$, from $C$.
This will be done by adding $2^n$ vertices.

I'll add Two new vertices between half of the pairs of two consecutive vertices is $C$
(The example will clear this sentence).

Denote $C = v_1, v_2 ,...v_{2^n},v_1$ where $\forall i\in[2^n]\ \ v_i\in \mathcal P(X)$

Let $C' = v_1,v_1\cup \{a\},v_2\cup \{a\},v_2,v_3,v_3\cup \{a\},v_4\cup \{a\},v_4...$

---

Propositions

1. $C'$ is a legal path in $G$
2. $\vert C'\vert = 2^{n+1}$
3. every vertex appears in $C'$ exactly once

Conclusion: $C'$ is a Hamilton path in $G$.