# Prove that this graph is nonplanar

Can anyone show me why this graph is nonplanar (which Mathematica assures me to be the case) ? 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.

• 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." – GAVD Oct 12 '15 at 10:17

You can find $K_5$ in your graph, here it is: I hope this helps $\ddot\smile$
• 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. – dtldarek Oct 12 '15 at 10:30