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$ Apr 6, 2012 at 18:52
  • $\begingroup$ Or the graph of any truncated polyhedron. $\endgroup$
    – Will Sawin
    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$ 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$ 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
    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
    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
    Apr 9, 2012 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.