For which $n$ is the $n$-dimensional hypercube a planar graph?
I've been asked the following question: For which values of $n$ is $Q_n$ a planar graph, where $Q_n$ is the $n$-dimensional hypercube? I succeeded to prove that for $n$ equal or greater than $6$ it won't be, but I know that actually $Q_n$ is a planar graph if and only if $n \leq 3$. Please help Thx
$\endgroup$ 31 Answer
$\begingroup$$K_{3,3}$ is a minor of $Q_4$, hence $Q_4$ is not a planar graph, and obviously $Q_4$ is a minor of $Q_n$ for any $n>4$, hence the only planar hypercubes are $Q_n$ with $n\leq 3$.
Another approach: $Q_4$ is a triangle-free graph, but any planar and triangle-free graph with $n$ vertices has at most $2n-4$ edges. $Q_4$ has $16$ vertices and $32>2\cdot 16-4$ edges, so $Q_4$ cannot be a planar graph.
Another approach may be to compute the Colin de Verdière graph invariant, since the spectrum of the adjacency matrix of $Q_n$ has a nice, easily-provable structure.
$\endgroup$ 6
