Prove two graphs are isomorphic. Let $G$ be a graph with $2^6$ vertices, each labelled with a $6$bit  string, if $u,v\in V_G$, $u\sim v \iff$ Their labels differ in exactly 5 digits.
Prove $G$ is isomorphic to the hypercube graph $Q_6$.
I know the statement for $u\sim v$ is equivalent to "their labels have exactly 1 digit in common" and thought that would help, but I didn't know to follow that.
I think the map 
$$f(b) = \begin{cases} b &\mbox{if odd number of ones }  \\ 
\overline b & \mbox{if even number of ones }\end{cases} $$
Should be an isomorphism, but then, I don't know how to prove that.
 A: Convince yourself that if two $6$-bit strings differ in $5$ positions, then one of them must have an even number of ones. To see why it is so, let one of the bit strings have an odd number of ones. Then the other bit string can either


*

*Agree with the first one on a position containing a $0$, and thus disagree on an odd number of $1$s (have an odd number of $0$s) and an even number of $0$s (have an even number of $1$s);

*Agree with the first one on a position containing a $1$ (already have one $1$), and thus disagree on an even number of $1$s and an odd number of $0$s (have an additional odd number of $1$s + the $1$ we counted before $\Rightarrow$ an even number of $1$s).


This means that applying the isomorphism you suggested to any two connected vertices means that one of them will be left intact, and the other one will have its bits flipped. Since they differed in $5$ positions, after flipping one of the vertex's bits, they now differ in $1$ position, which is precisely the condition for them to be connected in a hypercube graph.
