# 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$? Apr 6, 2012 at 18:52
• Or the graph of any truncated polyhedron. Apr 6, 2012 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... Apr 6, 2012 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? Apr 7, 2012 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. Apr 9, 2012 at 1:03

• 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. Apr 9, 2012 at 8:02