It seems obvious, but how to prove it properly? I tried Kuratowski, but got stuck at $K_{3,3}$

  • $\begingroup$ $K_{3,3}$ is not planar, so would not need to be checked if you are to show "the dual graph of a planar graph is planar". $\endgroup$ – coffeemath Dec 14 '13 at 9:54
  • $\begingroup$ Well I need to prove that no dual contains $K_{3,3}$ or $K_5$ or their division as a subgraph. For $K_5$ it's easy - 5 faces that are neighbours to each other? That's impossible by four colors theorem. But how to prove that $K_{3,3}$ in dual is impossible as well? $\endgroup$ – k5f Dec 14 '13 at 10:00
  • $\begingroup$ You don't really need to use Kuratowski to prove a graph is planar, provided you show it is planar by making a specific graph of it. I just put up an answer about how to do that from any given planar graph, that is to get its dual graph as a planar graph drawn on top of it. $\endgroup$ – coffeemath Dec 14 '13 at 10:05
  • $\begingroup$ The answer is wrong - check Eu Yu's comment. $\endgroup$ – k5f Dec 14 '13 at 10:10
  • $\begingroup$ I agree my answer was wrong as it initially used line graph instead of dual. Fixed now. $\endgroup$ – coffeemath Dec 14 '13 at 10:17

The dual graph of a planar graph is that connecting two regions iff they share a common edge. You can put a "dual-dot" somewhere in the interior of each face. Then you can connect two dual dots for faces that meet along an edge by drawing an arc connecting them which lies inside the two faces of the planar graph in which the dual dots lie, crossing the common edge. If this is done carefully, none of the added arcs will cross each other.

NOTE I had previously confused the line graph with the dual graph, and thanks to @EuYu for pointing that out. I hope this is OK now, as it at least is about the dual graph.

  • 2
    $\begingroup$ The dual graph is not defined this way. You're talking about the line graph. Note that line graphs of planar graphs are not necessarily planar. The $5$ star $K_{1,5}$ has line graph $K_5$ for example. $\endgroup$ – EuYu Dec 14 '13 at 10:03
  • 1
    $\begingroup$ @EuYu Thanks much for pointing out I had used the wrong definition, and also that line graphs aren't necessarily planar. $\endgroup$ – coffeemath Dec 14 '13 at 10:16
  • $\begingroup$ I don't think this is a real proof. I will use it though, and if my teacher likes it, I'll accept. $\endgroup$ – k5f Dec 14 '13 at 10:34
  • 2
    $\begingroup$ @MathN00b The thing that needs care is that the new edges don't cross each other. Initially put a mark on the interior of each edge. A given face may be mapped into a circle by some map $h$, then from the center $c$ of that circle one can draw radii to the points where the marks on the edges have moved under $h$. Then going back by $h^{-1}$ the radii become nonintersecting arcs going to the marked points on the edges of the given face. This done for all faces gives the copy of the dual graph. $\endgroup$ – coffeemath Dec 14 '13 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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