Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

enter image description here

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?

share|improve this question

4 Answers 4

up vote 9 down vote accepted

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.

Subdivision of K_{3,3}

share|improve this answer
    
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
2  
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)

share|improve this answer

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

share|improve this answer
    
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
    
+1 this is good enough. Btw I did not down vote. –  Mark 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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.