Can anyone show me why this graph is nonplanar (which Mathematica assures me to be the case) ?

A nonplanar graph

The graph passes the simple test $e \leq 3v - 6$.

I have tried and failed to find subgraphs isomorphic to subdivisions of $K_{3,3}$ or $K_5$.

The subgraph arising from deleting the right-most vertex and its adjacent edges is also nonplanar. In that subgraph, since only 3 vertices have degree 4, I suppose we cannot find a subdivision of $K_5$, so there must be a subdivision of $K_{3,3}$, but I cannot see it.

  • 2
    $\begingroup$ Let try with contracting edges. "A finite graph is planar if and only if it does not have K5 or K3,3 as a minor." $\endgroup$ – GAVD Oct 12 '15 at 10:17

You can find $K_5$ in your graph, here it is:


I hope this helps $\ddot\smile$

| cite | improve this answer | |
  • $\begingroup$ Thank you very much @GAVD and dtldarek ! dtldarek, may I ask how you proceeded ? Just by eyeballing it ?!?! Also how did you draw your lovely picture ? $\endgroup$ – Simon Oct 12 '15 at 10:22
  • 5
    $\begingroup$ For simple graphs it is quite easy to see (e.g. by eyeballing) if a graph is planar when it is planar. Thus, I tried to remove edges one by one without breaking non-planarity. While doing that I observed that the graph of crucial edges was not bipartite, so that ruled out $K_{3,3}$. After that, I started with 5 colors in 5 almost random vertices and colored their neighbors to form $K_5$. The diagram was done in Inksacpe. $\endgroup$ – dtldarek Oct 12 '15 at 10:30
  • $\begingroup$ That's brilliant, thank you dtldarek ! $\endgroup$ – Simon Oct 12 '15 at 10:33

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.