2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ What about $K_4$? $\endgroup$ Commented Apr 6, 2012 at 18:52
  • $\begingroup$ Or the graph of any truncated polyhedron. $\endgroup$
    – Will Sawin
    Commented Apr 6, 2012 at 18:57
  • 3
    $\begingroup$ 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... $\endgroup$ Commented Apr 6, 2012 at 20:19
  • $\begingroup$ 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? $\endgroup$ Commented Apr 7, 2012 at 5:16
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Commented Apr 9, 2012 at 1:03

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "...an edge cut of size two whose dual is a pair of parallel edges." $\endgroup$
    – JeffE
    Commented Apr 8, 2012 at 16:12
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Commented Apr 9, 2012 at 8:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .