Show that $G$ has a Hamiltonian cycle 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.
 A: 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.
A: 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


*

*$C'$ is a legal path in $G$

*$\vert C'\vert = 2^{n+1}$

*every vertex appears in $C'$ exactly once


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