# Prove that the tesseract graph is non-planar

The tesseract graph may be defined in various ways. I'm thinking of it as a subset lattice of the set $\{a,b,c,d\}$, where two subsets are adjacent if they differ in size by one, and one contains the other.

The tesseract is listed as non-planar on Wolfram MathWorld, but there is no proof given. I'm trying to prove it using Kuratowski's theorem, but I'm stuck. I feel certain I'm not going to find a copy of $K_5$ in the tesseract, but it seems there might be a copy of $K_{3,3}$ hiding in there. Does anyone see it?

Or would using Euler's formula be a better approach?

• If I collapse along the equivalence $a \sim c \sim ac$, $ad \sim bd \sim abd$ and $abc \sim bcd \sim abcd$, then the classes of $a$, $b$ and $abcd$ and the classes of $ab$, $bc$, $ad$ form a $K_{3,3}$, right? – darij grinberg Mar 24 '16 at 5:20 Looking at the tesseract above, contract a single edge in the red cycle (so it's a $3$-cycle), contract both orange cycles to a single point, and contract all the green edges to a single edge. This will result in $K_5$, so by Wagner's Theorem, the tesseract is non-planar.
Alternatively, if you really want to use Kuratowski's Theorem, here's a subgraph homeomorphic to $K_{3,3}$. 