N-Dimension Hypercube question? (making sense of the question)

Question

I just failed a test in discrete math. Here is the Question that cost me the most points:

An n-dimension hypercube f(n) is defined as follows. Basis Step: f(1) is a graph with 2 vertices connected by a link, and with 1-bit ID for each vertex.

Recursive step: To define f(n) for n>=2, we use two (n-1) dimension hypercubes. For one f(n-1), we append 0 to each of its vertex IDs and for the other f(n-1), we append 1 to each of its vertex IDs differ only in the left-most bit. Determine if the graph following graph is a two dimension hypercube. And then draw the graph for f(3)

For the first question I put "NO" because if the first graph is just two vertices connected by a straight line and it's considered a 1-dimension line. Then each additional vertices requires a new line which would add a dimension. Therefor the graph above would be more than two dimensions.

I was given ZERO points with no explanation by the Teacher as to the logic behind this.

The last question asks us to 'Prove' that the number of links in an n-dimension hypercube is n*2^(n-1) for all n>=1

At this point I was completely lost.

Answer 1

That picture is a two-dimensional hypercube. Notice how a given vertex $v$ is only adjacent to other vertices whose binary strings differ from $v$ by a single digit. A hypercube $Q_{n}$ has $2^{n}$ vertices with binary strings in $\{0, 1\}^{n}$.

For the edge count, consider a given vertex $v \in Q_{n}$. It has a binary string. How many binary strings differ from $v$ in exactly one place? Consider $010$. We have three such strings- $110, 011, 000$. So if we generalize, we have $n$ such vertices that $v$ is adjacent to. Now apply the handshake lemma. Each vertex has degree $n$. There are $2^{n}$ vertices. So $n2^{n} = 2E$.

Does that make sense?

Answer 2

Are you sure your test isn't due tomorrow? Cause I have that exact same question on mine. However, the graph is a two-dimensional hyper-cube. The way it's defined is that to create a new dimension you must copy the n-1 dimensional cube and connect the new vertices to the old one which is differentiated by 1 bit. Therefore how the lines interact don't matter so long as they connect to the correct place. 00->01 and 01->11

Answer 3

In 1-D the vertices are two, $\{(0),(1)\}$ How do you get the vertices of the 2-D cube? You take two copies of the 1-D cube and give the vertices a new bit, $0$ for the first copy and $1$ for the second, that is $\{(0,0),(1,0),(0,1),(1,1)\}$. Then you take all four, add a new bit to them which can be $0$ or $1$ to get $\{(0,0,0),(1,0,0),(0,1,0),(1,1,0),(0,0,1),(1,0,1),(0,1,1),(1,1,1)\}$ and so on. The $n$-D cube has $2^n$ vertices. Any pair of vertices are considered to be neighbors (and therefore linked) if you can go from one to the other by a flip of one of the bits. There are $n$ bits in each vertex so each vertex has $n$ neighbors. That gives us a total of $n2^n$ links. But now we 've counted every link twice (one joining say vertex a to vertex b and one joining b to a. So we have to divide by $2$ to get $n2^{n-1}$. Or you can go by induction on $n$. The edges of the $n$-D cube are twice the edges of the $(n-1)$ Dimensional since you have two copies, plus the new vertices that connect each vertex from the first copy to one from the 2nd copy, i.e. $f(n)=2f(n-1)+2^{n-1}$. That together with $f(1)=1$ is all you need.