Complement of the $3$-dimensional Cube $\overline {Q_3}$ is nonplanar

I was asked the question

Prove that the compliment of the $3$-dimensional Cube, $\overline {Q_3}$ is not planar.

I tried using $e\leq 3v-6$ but that doesn't work in this case since $e=16$ and $v=8$. Also, I tried finding a $K_{3,3}$ or a $K_5$ in it which I couldn't. I also know how to write $Q_3$ as binary $3$-sequences, but that didn't help either.

Any ideas how to do it?

We can label the vertices of ${Q_3}$ with binary sequences of length three. Two vertices are adjacent if they differ in exactly one coordinate. So for instance $110$ and $010$ are adjacent vertices. ${Q_3}$ is a bipartite graph with the partition sets of four vertices each being determined by whether a vertex has an even or an odd number of $1$s in its coordinates. Let me refer to these as the even vertex set ($E=\{000,011,101,110\}$ and $O=\{001,010,100,111\}$)

In the complement, all the $E$ vertices are connected, forming a $K_4$; and likewise for all the $O$ vertices. Additionally each even vertex will have one (complementary) odd neighbor--for instance $011$ will be adjacent to $100$.

If we collapse the odd vertices and the corresponding $K_4$ into a single vertex, the resulting graph (the four even vertices, and the one big odd vertex) will be a $K_5$ which is nonplanar.

Edit: To more explicitly show the steps of how the complementary graph is nonplanar: Using the vertex numbering suggested above: Remove the three edges forming the triangle from 001 to 010 to 100 and back to 001. These three vertices now each have degree two and so can be 'smoothed' (removed, and merging the two edges into a single edge through the removed vertex). This results in a $K_5$. I believe these are all legit steps in showing nonplanarity.