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

I've been given that the above graph is planar, but I can't for the life of me redraw it so that none of the edges intersect: the last(10th) edge I draw in on my rough paper always produces an intersection. Will someone prove or disprove the planarity of this graph?

share|improve this question
2  
This question reminds me of the game planarity. You should play it, then this challenge would seem easy :) planarity.net –  muzzlator Mar 16 '13 at 15:33

4 Answers 4

up vote 4 down vote accepted

This is the wheel graph $W_6$:

wheel graphs

(taken from Wikipedia)

share|improve this answer
2  
(I was trying to get the OP to come up with this by themselves.) –  Tara B Mar 16 '13 at 15:34
    
@TaraB Your answer has reinforced what I had crucially forgotten: that edges are allowed to "cut through" one another when "rearranging" a graph to find an appropriate isomorphism, and that I don't have to restrict myself to the 2-d plane when doing so. Not sure if I'm making sense but thank you, Colin and Tara! –  Ryan Mar 16 '13 at 15:46
    
@Ryan: No problem! I'm glad it helped. Graph isomorphism isn't nearly as complicated as you were making it! =] –  Tara B Mar 16 '13 at 15:48
    
Note that you don't even have enough information to say whether two edges 'cut through' each other when you rearrange, since the drawing of a graph doesn't carry information about which edge is 'on top'. –  Tara B Mar 17 '13 at 11:36

enter image description here

enter image description here

Then just move the six in the center.

share|improve this answer
    
Thank you for the illustration. –  Ryan Mar 16 '13 at 15:49

It is planar. Try numbering the five outer vertices and then rearranging them so that you still have the same edges, but now none of them cross. (Hint: if you number them 1 to 5 clockwise from the top, then since there is an edge between 1 and 3, it'd probably help to move 3 to the current position of 2.)

share|improve this answer

A finite graph is planar iff it doesn't contain either $K_{3,3}$ or $K_5$ as a minor. It's easy to eliminate both possibilities for this graph, so it is planar.

share|improve this answer
    
Hi Peter, thanks; has this got to do with subdividing and/or contracting graphs? If so, could please provide some elaboration? I'm struggling to understand these related ideas, and would much appreciate your input. Thank you. –  Ryan Mar 16 '13 at 15:41
    
This is a theorem which you may see later on in a graph theory course. If you haven't seen it yet, I wouldn't worry about it too much for now, though it's very nice. In this particular case I think it's much easier to show the graph is planar by exhibiting a planar embedding than by showing it has no $K_{3,3}$ or $K_5$ minor! –  Tara B Mar 16 '13 at 15:49
    
So what Peter said is indeed related to Kuratowski's Thm? Well, I've already seen it in the course, but the coverage was very patchy. Help? –  Ryan Mar 16 '13 at 15:55
    
@Ryan, what I stated is (a slight misquote of - I'll correct it) Wagner's theorem, but it's closely related to Kuratowski's theorem. –  Peter Taylor Mar 17 '13 at 8:28
    
Thanks, Peter. Time to do some googling. –  Ryan Mar 17 '13 at 17:11

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.