Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The dual graph of a planar graph is the graph formed by placing one vertex in every cell and one edge between the vertices of adjacent cells.

A graph is 2-vertex-connected if removing any one vertex does not disconnect the graph, and 3-vertex connected if removing any two vertices does not disconnect it. It is 3-regular if every vertex has degree 3.

Let G be a graph that is planar, 2-vertex connected, and 3-regular, but not 3-vertex-connected.

Does the dual of G have at least one pair of vertices with two or more edges between them? In other words, does the dual of G necessarily have a multiedge?

*Edit: neglected to mention the lack of 3-vertex-connectivity.

share|improve this question
1  
What about $K_4$? –  Gjergji Zaimi Apr 6 '12 at 18:52
    
Or the graph of any truncated polyhedron. –  Will Sawin Apr 6 '12 at 18:57
3  
Unless, you ask only for graphs which are 2-connected but not 3-connected in which case it is true by an easy case check... –  Gjergji Zaimi Apr 6 '12 at 20:19
    
Ah, yes, I neglected to mention the lack of 3-connectivity - that's why I'd defined it! What's the case check involved? Are there a finite # of such graphs? –  Simplicial Question Apr 7 '12 at 5:16
    
Given such a graph, and taking a face far away from the domain where 3-connectivity fails, you can split it in two by adding two vertices to two of its edges and connecting them. This will not lose you 2-connectivity. This easily gives you an infinite family. –  Will Sawin Apr 9 '12 at 1:03

1 Answer 1

The edge connectivity and vertex connectivity of 3-regular graphs are equal. So if the the graph is 2-connected the it has an edge cut of size two which is going to be a multiple edges. As for why the edge connectivity and vertex connectivity are equal just consider a vertex cut of minimum size; its deletion would separate the graph into at least two components. Just count the edges that goes from the vertex cut to the each component.

share|improve this answer
    
"...an edge cut of size two whose dual is a pair of parallel edges." –  JeffE Apr 8 '12 at 16:12
    
The edge connectivity being equal to the vertex connectivity also follows trivially from Menger's Theorem. In a 3-regular graph, two $s$-$t$ paths are internally vertex disjoint if and only if they are edge-disjoint. –  Tony Huynh Apr 9 '12 at 8:02

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.