3.5f Hypercubes

Graph Representation of a Hypercube

An $n$-dimensional hypercube can be represented as a graph $G=(V,E)$ with $V=\{0,1{\}}^n$ vertices, where $V$ is the set of all $n$-bit strings. Two vertices of a hypercube are connected by an edge if and only if the two vertices differ in exactly one bit position.

Recursively, an $n$-dimensional hypercube is the result of joining two $(n-1)$-dimensional hypercubes with vertices $0x$ and $1x$ where $x\in \{0,1{\}}^{n-1}$.

Properties

(Hypercube Vertices) For an n-dimensional hypercube, $v=2^n$.

1. Base Case: A 0-dimensional hypercube has $2^0=1$ vertex by inspection.
2. Hypothesis: Assume that the theorem holds for $n$ dimensions.
3. Inductive Step: We see that for $n+1$, $v=2(2^n)$, and therefore the theorem holds for all $n$.

(Hypercube Edges) For an n-dimensional hypercube, $e=n{2}^{n-1}$.

We observe that the degree of each vertex of an $n$-dimensional hypercube is exactly $n$. Simultaneously, we observe that each edge is counted twice. Therefore, $e=\frac{n{2}^n}{2}=n{2}^{n-1}$.

(Recursively, )

(Hypercube Connectivity)