Welcome to MathOverflow

Question

1

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.

edited Apr 7 2012 at 5:16

asked Apr 6 2012 at 18:27

Simplicial Question
29●2

1

What about $K_4$? – Gjergji Zaimi Apr 6 2012 at 18:52

Or the graph of any truncated polyhedron. – Will Sawin Apr 6 2012 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 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? – Simplicial Question 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. – Will Sawin Apr 9 2012 at 1:03

w g · Answer 1 · 2012-04-08 10:58:10Z UTC

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.

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.