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

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

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.
• 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? – audiFanatic Apr 16 '14 at 6:56