Prove that if graph $G$ is a 3-connected planar graph then its dual must be simple.
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.
Related videos on Youtube
audiFanatic
Updated on August 01, 2022Comments
-
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.
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 over 9 yearsSince 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?