[Math] Does the dual of every planar, 3-regular, 2-connected graph have a multiedge

graph theory

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.

Best Answer

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.

Related Question