Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

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|improve this answer
    
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 at 6:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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