Prove that a complete hypercube graph is connected. i.e. there is a path between every pair of vertices. Prove that a HyperCube graph is connected. i.e. there is a path between every pair
of vertices.
I was able to find proof for bipartite, but I'm curious how hypercube is related.
 A: OK, let's fix a natural $n$. Let $X$ be a set with $n$ elements.
The $n$-dimensional hypercube graph is defined as $G = (V, E)$, where $V = \mathcal{P}(X)$ is the power set of $X$, and $E$ consists of all the pairs of subsets $A, B \subseteq X$ that differ by exactly one element.
For any $A, B \subseteq X$, let us denote by $d(A, B)$ the number of elements in the symmetric difference of $A$ and $B$: $d(A, B) = |A \triangle B|$.
Let us prove by induction on $k$ the following statement: for every $A, B$ such that $d(A, B) = k$, there is a path in $G$ from vertex $A$ to vertex $B$. Clearly, if we manage to prove this for all nonnegative integers $k$, we will prove that $G$ is connected.
The base of induction is easy: for $k=0$, if $d(A, B) = 0$, then $A \triangle B = \varnothing$, so $A=B$ and there is an empty path from $A$ to itself.
Now the transition. Suppose we have proved the statement for some $k$, and $d(A, B) = k + 1$. We need to show that there is a path in $G$ from $A$ to $B$. The set $A \triangle B$ contains $k+1$ elements, so it is nonempty. Pick any $x \in A \triangle B$ and set $C = A \triangle \{x\}$.
$A$ and $C$ differ by a single element, so there is an edge between $A$ and $C$. It remains to show that there is a path from $C$ to $B$. Observe that $$C \triangle B = (A \triangle \{x\}) \triangle B = (A \triangle B) \triangle \{x\} = (A \triangle B) \setminus \{x\}.$$
Then $d(C, B) = |(A \triangle B) \setminus \{x\}| = (k+1)-1 = k$, and by induction hypothesis there is a path from $C$ to $B$. The proof is complete.
PS: I don't see any connection with complete bipartite graphs. Yes, the hypercube graph is bipartite, but so what?
A: The hypercube graph $Q_n$ is defined to be the graph with vertex set the bit strings of length $n$ (i.e. $V(Q_n)=\{0,1\}^n$), with two vertices adjacent if and only if the corresponding bit strings differ in exactly one coordinate.  Thus, in $Q_4$, the vertex 0010 has 4 neighbors, and the bit strings corresponding to each of the 4 vertices can be obtained by flipping exactly one of the 4 coordinates of 0010.  Thus, its 4 neighbors are 1010, 0110, 0000, and 0011.  
Given any two bit strings of length $n$, if they differ in exactly $k$ coordinates, then we can start at the first string, and by flipping one of the $k$ coordinates at a time, eventually obtain the second string.  Thus, there is a path between these two vertices of length exactly $k$.  In fact, this is also a shortest path: the shortest path between any two vertices in the hypercube has length exactly equal to the number of coordinates where the two corresponding strings differ in their bit values.  When $k \ge 2$, there are many such shortest paths between the two given vertices since the order in which we pick which of the $k$ bits to flip during each step is not unique.
In $Q_6$, the vertices 000000 and 111111 are a distance 6 apart, as are the vertices 111001 and 000110.  The diameter of $Q_n$ is $n$.
