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?

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)
