= Hypercube subdivision of the utility graph
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\to0111\to0110\to0100$, $1100\to1101\to0101\to0001$, and $1100\to1110\to1010\to0010$. Their internal vertices are distinct. Appending zero coordinates embeds the construction in every higher-dimensional cube, proving nonplanarity.
Back to article page
