Hypercube graph ($Q_d$)

The $d$-dimensional hypercube graph has vertex set $\{0,1{\}}^d$ and joins two vertices exactly when they differ in one coordinate. It is a $d$-regular bipartite graph on $2^d$ vertices.

The four-dimensional hypercube contains a graph subdivision of $K_{3,3}$, although no hypercube contains an ordinary $K_{3,3}$ subgraph: two distinct cube vertices have at most two common neighbors. One subdivision uses branch sets $\{0000,0011,1100\}$ and $\{0001,0010,0100\}$. Six connections are direct; the remaining paths are $0011\to 0111\to 0110\to 0100$, $1100\to 1101\to 0101\to 0001$, and $1100\to 1110\to 1010\to 0010$. Their internal vertices are distinct. Appending zero coordinates embeds the construction in every higher-dimensional cube, proving nonplanarity.

A Gray code orders binary strings so that successive strings differ in exactly one bit. Consequently it describes a path in a hypercube graph; a cyclic Gray code describes a cycle.