5
$\begingroup$

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.

$\endgroup$
1
  • 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$ Commented Oct 12, 2015 at 10:17

1 Answer 1

Reset to default
7
$\begingroup$

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

K5

I hope this helps $\ddot\smile$

$\endgroup$
3
  • $\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$ Commented Oct 12, 2015 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$ Commented Oct 12, 2015 at 10:30
  • $\begingroup$ That's brilliant, thank you dtldarek ! $\endgroup$ Commented Oct 12, 2015 at 10:33

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.