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