Prove that if graph $G$ is a 3-connected planar graph then its dual must be simple.

1,677

You'ra on the right track. Every edge of the dual is corssed by an edge of $G$, hence a cycle of length $k$ in the dual graph gives us $k$ edges of $G$ with one endpoint in the interior and one endpoint in the exterior of the cycle. Thus removing theses $k$ edges from $G$, we obtain a nonempty interior and a non empty exterior component of $G$ (or maybe even mre components). By assumption, this is not possible unless $k\ge 3$, hence no cycle oflength $2$ (multi-edge) or $1$ (loop) exists.

Share:
1,677

Related videos on Youtube

audiFanatic
Author by

audiFanatic

Updated on August 01, 2022

Comments

  • audiFanatic
    audiFanatic over 1 year

    I'm trying to study for a quiz. I think I'm on the right track with this problem, however, I'm having a difficult time formalizing it.


    Prove that if graph $G$ is a 3-connected planar graph then its dual must be simple.

    By simple we mean no self-loops nor multiple edges between the same pair of vertices. The problem doesn't specify whether we're discussing directed graphs or not, I would assume not though.


    My idea is that if $G$ is 3-connected (In other words, the graph may be disconnected by removing a minimum of 3 edges), then the edges which make up the cutset would form 2 internal faces (excluding the infinite face). So when we take the dual of $G$, these two faces become vertices as shown with my crude Paint skills below.

    enter image description here

    Now supposing G was not 3-connected, but instead 2-connected. Then we would only have one internal face and two edges running between the internal face and the infinite face, which creates a general graph, not a simple one, as there are multiple edges between the same vertices.

    So perhaps proof by contradiction would be best here I'm assuming?

  • audiFanatic
    audiFanatic over 9 years
    Since a cycle must return to its starting vertex, a cycle beginning in $G_1$ must end in $G_1$ (it may or may not cross into $G_2$). In other words, the cycle must cross the bridges between $G_1$ and $G_2$ never or an even number of times. So that means such a cycle can only occupy two of the three available edges or none at all. Supposing the first case, if we removed the 2-occupied edges as you suggest, aren't we going to get a self-loop in the dual going across the remaining edge, which is not a simple graph?