Planarity of 4-dimensional hypercube graph with 2 adjacent vertices deleted

Question

I have already used some of the inequalities discussed in my graph theory class (e ≤ 3v − 6 etc.) which seem to be giving me nothing thus far. I'm trying to apply Kuratowski's theorem to see if it contains subgraphs that are subdivisions of $K_{3,3}$ or $K_5$ but it isn't really clear to me how to search for these or what I should be looking for in general.

Answer 1

We shall apply the same observation which is used to show non-planarity of $K_{3,3}$.

First, we remark that the graph of any $d$-dimensional cube is bipartite, because we can consider its vertex set as $\{0,1\}\subset \Bbb Z^d$ with the color classes consisting of vertices with odd and even sum of coordinates, respectively.

Now let $G$ be an arbitrary planar bipartite graph. For instance, we can pick as $G$ the mysterious graph $Q^4_-$ from your question or the famous $K_{3,3}$.

Let $G$ has a plane drawing with $n$ vertices, $m$ edges, and $k$ faces. By Euler’s formula, $n-m+k=2.$

Now double count a number $N$ of pairs $(e, f)$ where $e$ is a edge of the graph $G$ incident to its face $f$. Since $G$ is bipartite, each its face $G$ has even degree, so it is at least $4$. Thus each face $f$ of $G$ contributes at least $4$ to the sum for $N$, implying $N\ge 4k$. On the other hand, each edge $e$ of $G$ is incident to exactly $2$ faces (we also count the outer face, if needed), so it contributes exactly $2$ to the sum for $N$, implying $N=2m$. Thus $2m=N\ge 4k$.

Combining the obtained inequality with Euler’s formula, we obtain $k=2+m-n\le m/2$, or $m+4\le 2n$.

For the graph $Q^4_-$ we have $n=2^4-2=14$. To calculate $m$ we remark that each vertex of $4$-dimensional cube has degree $4$, so it has $2^4\cdot 4/2=32$ (we divided by $2$ because we double counted each edge), so when we remove from the cube two adjacent vertices we remove also $4+4-1=7$ edges (we subtract $1$, because we double counted the edge between removed vertices). Thus $m=32-7=25$.

Finally, we see that $m+4=25+4=29>28=2n$, so the graph $Q^4_-$ is non-planar.