# Is this star-shaped graph planar?

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?

-
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

This is the wheel graph $W_6$:

(taken from Wikipedia)

-
(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

Then just move the six in the center.

-
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.)

-

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.

-
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