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$ 6More in general
"Zoraya ter Beek, age 29, just died by assisted suicide in the Netherlands. She was physically healthy, but psychologically depressed. It's an abomination that an entire society would actively facilitate, even encourage, someone ending their own life because they had no hope. Th…"
