I'm dealing with some hypercube questions here. The one I'm currently on states:
Find the maximum distance between pairs of vertices in $Q_8$. Give an example of one such pair that achieves this.
I've got the first part of the question down. I drew out $Q_1, Q_2, Q_3, Q_4$, realized that the maximum distance between vertices in $Q_n$ is $n$. After realizing this, it began to make sense to me. $Q_{n+1}$ is created by duplicating $Q_n$ and connecting corresponding vertices. Each vertex from $Q_n$ is connected to exactly one more vertex, and so the maximum distance between vertices will increase by exactly one.
That was the easy part.
How would I possibly show this? I mean. I could spend hours figuring out how to draw $Q_8$, then label all the vertices, and finally present a sequence of eight edges.. But that doesn't sound like the way a mathematician would solve such a problem so it can't possibly be the correct way…
Any help is greatly appreciated!
Best Answer
Think of it this way. If you have a cube in $3$ dimensions then we can embed the cube into $\mathbb{R}^3$. We label the vertices of the cube as the set of the binary sequences of length $3$. For example $(0,\ 0,\ 0)$ will represent the vertex at the origin while $(1,\ 1,\ 1)$ will represent the opposite corner. The vertices which are adjacent are precisely the sequences which differ by $1$ and only $1$ component (corresponding to moving one step in that dimension).
It is perhaps more intuitive to see how we can traverse the cube now. The distance between two vertices will be the number of different entries between the binary representations of the vertices.
You can verify that in general, the hypercube graph in $n$ dimensions $Q_n$ is given similarly in terms of binary sequences of length $n$ and that the distance property still holds. Now we have $n$ entries representing a vertex, so given any vertex, the furthest we can be away from it is for every entry to be different for a total of $n$ different entries. Therefore the furthest we can traverse from any vertex is $n$ steps.
Notice that this also explicitly gives you which vertices are distance $n$ away from each other, we simply take the complement of the vertex's binary representation (change $0$s to $1$s and vice versa).