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?
What is a rigorous way to prove that this graph is non-planar?
4
$\begingroup$
graph-theory
planar-graphs
4 Answers
10
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.
-
2The hard direction of Kuratowski's is unnecessary: you only need the easy direction. – 2011-07-15
5
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)
3
A reference to Kuratowski's theorem may be seen here.
-
0I 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. – 2011-07-15
2
Some tests of (non) Planarity [in increasing order of applicability and somewhat difficulty]
- Show that Euler's Formula cannot be satisfied.
- Try to find an embedding of $K_{3,3}$ or $K_5$, or its subdivisions/minors in your graph.
- Find the average number of edges per face. It should be greater than 3, else non-planar.
- Some combinatorial/geometric argument along with some partial restrictions got by using the above techniques.