What is a rigorous way to prove that this graph is non-planar?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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)