# Does the dual of every planar, 3-regular, 2-connected graph have a multiedge?

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.

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

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.

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