3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – darij grinberg Mar 24 '16 at 5:20
  • $\begingroup$ There is a $K_5$ minor, but it's hard to describe how to get it. :) $\endgroup$ – Mike Pierce Mar 24 '16 at 5:20
3
$\begingroup$

Tesseract1

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}$.

Tesseract2

$\endgroup$
  • 1
    $\begingroup$ Those both make sense. Thank you very much! :) $\endgroup$ – G Tony Jacobs Mar 24 '16 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.