# Hypercube Maximum Distance, Graph Theory

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!

-

## 3 Answers

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).

-
Ahhh.. I forgot that $Q_n$ already has labels. So my example of a path of length $8$ in $Q_8$ would be a sequence of 9 binary strings that represent vertices, each differing by exactly 1 digit. Correct? –  connorbode Nov 8 '12 at 18:00
Yes, that would be it. –  EuYu Nov 8 '12 at 18:33

You can think of $Q_n$ as a graph whose vertices are the $2^n$ $n$-tuples $\langle b_1,\dots,b_n\rangle$ with each $b_k\in\{0,1\}$. Two vertices are adjacent if they differ in exactly one coordinate. The distance between two vertices vertices is the number of coordinates in which they differ. (This requires proof, but it’s not too hard.) Now, what vertex of $Q_n$ is maximally distant from $\langle\underbrace{0,0,\dots,0}_n\rangle$?

-

You have basically already sketched a proof by induction. The base case $Q_1$ is obvious. Given that the maximum distance in $Q_n$ is $n$, consider $Q_{n+1}$ as the Cartesian product $Q_n\square K_2$. The maximal distance between vertices in one copy of $Q_n$ is $n$, and the maximal distance between points in different copies is at least $n+1$, since you have to switch copies at least once, and also at most $n+1$, since you can reach each point by switching copies only once, so it's $n+1$. Thus by induction the maximal distance in $Q_n$ is $n$.

-