# What is a rigorous way to prove that this graph is non-planar? What is a rigorous way to prove this graph is non-planar? I have some vague memories of setting the edges within the boundary of the graph as vertices and then use some adjacency rule to check to see if it's bipartite (or something like that to check for planarity). Could someone tell me how to do it properly?

Kuratowski's Theorem provides a rigorous way to classify planar graphs. To show that your graph, $G$, is non-planar, it suffices to show that it contains a subdivision of $K_{3,3}$ as a subgraph.

But the following graph is a subdivision of $K_{3,3}$ and a subgraph of $G$, so we're done. • How did you draw such a nice graph? – Mark Jul 15 '11 at 12:38
• @Mark: Thanks. I used Inkscape. – Ben Derrett Jul 15 '11 at 12:45
• And even without Kuratowski's Theorem, once you have this picture you just have to prove $K_{3,3}$ is non-planar, for which see Joseph Malkevitch's answer (supplemented by the observation that if it were planar it would have no region with just three edges). – Gerry Myerson Jul 15 '11 at 13:08
• The hard direction of Kuratowski's is unnecessary: you only need the easy direction. – Qiaochu Yuan Jul 15 '11 at 14:42

Try starting by proving the non-planarity of the 6 vertex analogue of the graph you drew using Euler's formula for plane graphs (V + F - E = 2)

A reference to Kuratowski's theorem may be seen here.

• I guess the OP wants to see a $K_5$ or a $K_{3,3}$ explicitly embedded into his graph. – lhf Jul 15 '11 at 12:31
• @ncma, you're making him work for his answer.... – Gerry Myerson Jul 15 '11 at 12:34
• I am trying to avoid giving away the shop. This appeared to be an exercise of some kind to me and I don't want to "ruin" it. – ncmathsadist Jul 15 '11 at 13:41

Some tests of (non) Planarity [in increasing order of applicability and somewhat difficulty]

1. Show that Euler's Formula cannot be satisfied.
2. Try to find an embedding of $K_{3,3}$ or $K_5$, or its subdivisions/minors in your graph.
3. Find the average number of edges per face. It should be greater than 3, else non-planar.
4. Some combinatorial/geometric argument along with some partial restrictions got by using the above techniques.