n-dimension hypercube!

405 Views Asked by At

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\geq2$, 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)$

enter image description here

a) Draw the graph for $f(3)$

b) Prove' that the number of links in an $n$-dimension hypercube is $n2^{n-1}$ for all $n\geq1$

1

There are 1 best solutions below

0
On

A hypercube $Q_{3}$ has $2^{3} = 8$ vertices. So your drawing is incorrect.

As for the edge count, take a vertex $v$, which is a string in $\{0, 1\}^{3}$. How many strings can differ from $v$ in exactly one place? Only three strings, right? So by the handshake lemma, we have $3 * 2^{n} * \dfrac{1}{2} = 3 * 2^{n-1}$ edges. Now generalize this to $n$ and the proof is exactly the same.