The connectedness of dual graph

Question

Prove: if a planar graph $G$ is $k$-vertex-connected, then so do its dual $G^{\ast}$ for $k=2,3$. And find a counterexample for $k=4$.

I only have a vague idea for $k=2$: if $G$ has a cut vertex, then it will look like a claw. Once we remove the vertex of the outer face in $G^{\ast}$, it is impossible for two non-adjacent inner faces to be connected.

I doubt whether this could be called a rigorous proof, since it highly relies on geometrical intuition. And this method fails for $k=3$.

The example for $k=4$ is as follows: put a triangle $B_1B_2B_3$ inside another one $A_1A_2A_3$, and connect all edges $A_iB_j$ as long as $i\neq j$. The dual graph is 3-regular, which cannot be 4-connected.

Answer 1

As @Licheng noticed, we need to be clear on the requirements for the graph $G$. From the similar questions mentioned by @Licheng, $G$ is supposed to be simple.

The proof is not that hard, but there are a lot of details to make it rigorous.

We start with some results, stated without proof:

Theorem : The cycle space of a planar graph $G$ is the cut space of its dual $G^*$

Corollary 1: $G$ has a self loop $\iff$ $G^*$ has a $1$-edge cut (a bridge).

Corollary 2: $G$ has an edge of multiplicity $\geq 2$ $\iff$ $G^*$ has a $2$-edge cut.

Corollary 3: $G$ is simple $\iff$ $G^*$ is $3$-edge connected.

We can then show:

Theorem 1: If $G$ is simple and $2$-vertex connected, then it implies $G^*$ is $2$-vertex connected and has no loops.

proof: We show it by contraposition:

• If $G^*$ has a loop, then $G = G^{**}$ has a $1$-edge cut, hence it has a $1$-vertex cut, so $G$ is not $2$-vertex connected.

• If $G^*$ has a $1$-vertex cut (and no loop), let $u$ be the cut vertex, and let $G_1$ and $G_2$ be two disconnected subgraphs that appears after removing $u$.

  $u$ must be connected to at least one $G_1$ vertex, and one $G_2$ vertex. There is at least one face $f$ with the pattern $G_1-u-G_2$. If we follow the vertices of the face from $u$ in the $G_1$ direction, we can't go directly from a vertex of $G_1$ to a vertex of $G_2$, because these graphs are disconnected, so we will need to meet again $u$ before reaching $G_2$. So $f$ has the following pattern: $... G_2 - u - G_1 - ... - G_1 - u - ...$. We will denote $CG_1$ the connected component of $G_1$ containing the vertices of $G_1$ appearing in this pattern, and $CG_2$ the connected component of $G_2$ containing the vertex of $G_2$ appearing in this pattern.

  If the graph induced by the vertices of $CG_1$ and $u$ has no faces (besides $f$), then it must be a tree and it will have a bridge, so $G$ will have a loop. We apply the same line of reasoning to $CG_2$

  We can know assume the graph induced by the vertices of $CG_1$ and $u$ has at least a face, say $f_1$. We can also assume the graph induced by the vertices of $CG_2$ and $u$ has at least a face, say $f_2$. When deleting vertex $f$ in $G$ (faces are vertices in the dual), $f_1$ and $f_2$ will be disconnected, so $f$ is a cut-vertex of $G$, so $G$ is not $2$-connected.

Theorem 2: If $G$ is simple and $3$-vertex connected, then equivalently $G^*$ is simple and $3$-vertex connected

proof: We show it by contraposition:

• If $G^*$ is not simple, then $G^*$ has a $1$ or $2$-edge cut, hence it has a $2$-vertex cut so $G$ is not $3$-vertex connected.

• If $G^*$ has a $2$-vertex cut, let $u$, $v$ be these two cut vertices, and let $G_1$ and $G_2$ be two disconnected connected graph that appears after removing $u$ and $v$.

  In the first time, we will suppose that there is no edge between $u$ and $v$, so $u$ and $v$ have only neighbors in $G_1$ or $G_2$.

  If there is a face with a pattern like $...-G_1-u-G_2...-G_2-u-...$, we can apply the same reasoning than in theorem $1$ to prove that there is a one vertex cut, so we can now assume no such pattern exist.

  Both $u$ and $v$ needs to be connected to both $G_1$ and $G_2$. By turning clockwise on the neighbors, we will find both a vertex of $G_1$ followed by a vertex of $G_2$, defining a face $f_1$, and a vertex of $G_2$ followed by a vertex of $G_1$ defining a face $f_2$. For a face with the pattern $G_1-u-G_2$, by following the contour of the face, we get the pattern: $u-G_1-...-G_1-v-(...-v)^*-G_2-...-G_2-u$.

  By combining the patterns of $f_1$ and $f_2$, we then get the pattern:

  We define $CG_1$ the graph induced by $u$, $v$ and the vertices of the connected component of $G_1$ containing the $G_1$'s vertices of $f_1$ and $CG_2$, and we define $CG_2$ similarly.

  If $CG_1$ contains no faces, then $u$ and $v$ must have only one neighbors in $CG_1$, and this defines a $2$-edge cut. Same applies for $CG_2$.

  If both $CG_1$ and $CG_2$ have a face, these faces are separated by $f_1$ and $f_2$, thus it defines a $2$-vertex cut in $G^*$, so a multi-edge in $G$

  Now if there is an edge between $u$ and $v$, we delete it, and applies the above reasoning. Adding it back does not discard the reasoning on pattern $...-G_1-u-G_2...-G_2-u-...$, nor when $CG_1$ or $CG_2$ has no faces. Otherwise, $u-v$ split may split $f_1$ or $f_2$ in two parts, but we can keep only one of these two parts, and it will still define a $2$-vertex cut.

Answer 2

This question has been mentioned multiple times on this stack. Unfortunately, it has not been seriously addressed.

• Dual of a planar 2-connected graph
• Show that if G is a planar, simple and 3-connected graph, then the dual graph of G is simple and 3-connected

I can find some literature that describes the results you mentioned.

• "Ziegler G M . Lectures on Polytopes: Updates. 1998". ( in chapter Steinitz' Theorem for 3-Polytopes).

Alternatively, we can take a look at the lecture notes below (Proposition 9).

• https://dccg.upc.edu/irp2018/wp-content/uploads/2018/04/Notes_BojanMohar.pdf

A plane graph $G$ is 2-connected if and only if its dual $G^∗$is 2-connected. It is 3-connected if and only if $G^∗$ is 3-connected.

However, none of them provide a direct proof.

---

Here, I can provide some visual evidence, but it may not be very rigorous.

First, since dual graphs may have loop edges and multiple edges, we need to be careful with the definition of 2-connectedness for multigraphs. I give the following example. The black vertices and edges below represent a plane graph, while its dual graph is represented by red vertices and edges. Clearly, $G$ is not 2-connected. The next question is, is $G^*$ 2-connected? (I will assume for now that it is not 2-connected, otherwise I would have found a counterexample.)

First, we give the following two Lemmas (without proof):

Lemma 1 Let $G$ be a plane graph. Then $G^*$ is a connected plane graph.

Lemma 2 Let $G$ be a connected plane graph. Then $G^{**}=G$.

Theorem 1. Let $G$ be a 2-connected plane graph. Then $G^∗$ is 2-connected.

Proof. Suppose that $G^*$ is not 2-connected. Combing the assumption with Lemma 1, $G^*$ is connected and contains a cut vertex. Clearly, $G^*$ can not be a tree, otherwise, $(G^*)^*$ is isomorphic to a single isolated vertex with several loops, which is not 2-connected. By Lemma 2, $G=G^{**}$ , and thus $G$ is also not 2-connected, a contradiction.

Claim 1. Every block of $ G^*$ is 2-connected.

Proof: If not, $G^{**}$ (also $G$) contains loops and is also not 2-connected, as initially defined, a contradiction.

By Claim 1, $G^*$ has two adjacent 2-conencted blocks, $B_1$ and $B_2$. $G^*$ has at least two facial cycles, $C(f_1)$ and $C(f_2)$, which lie on $B_1$ and $B_2$. Their bounded faces correspond to vertices $f_1^*$ and $f_2^*$ in $G^{**}$, respectively. Any path between $f_1^*$ and $f_2^*$ must pass through the vertex $v$ in $G^{**}$ corresponding to the common face of $B_1$ and $B_2$. The vertex $v$ is a cut vertex in $G^{**}~(=G)$. This contradicts the fact that $G$ is 2-connected.

If we want to consider 3-connectedness, we may continue the simliar approach.

Answer 3

I recently discovered a proof using Menger's theorem. It is essentially the same as @caduk.

Menger's theorem

1. Let $A,B$ be two sets of vertices, then the minimum number of vertices separating them equals the maximum number of disjoint paths connecting them.
2. $G$ is $k$-connected if and only if there are $k$ disjoint paths between any two vertices in $G$.

Proof
Let $G$ be a $3$-connected planar graph, we need to find $3$ paths between any two vertices $f_1,f_2$ in $G^{\ast}$. Since each face in $G$ uses at least three edges as its boundary, $d_{G^{\ast}}(f_1),d_{G^{\ast}}(f_2)\geq 3$. Take $A=\{v_1,v_2,v_3\};B=\{u_1,u_2,u_3\}$, three vertices on the boundary of $f_1,f_2$ respectively.

According to Menger's theorem, there are three disjoint paths: $v_1P_1u_i,v_2P_2u_j,v_3P_3u_k$ between $A,B$ in $G$, which induces $e_{v_1}P_1e_{u_i},e_{v_2}P_2e_{u_j},e_{v_3}P_3e_{u_k}$ between $f_1$ and $f_2$ in $G^{\ast}$. Here, $e_{v_m}$ is the dual edge of the one on the boundary of $f_1$ incident to $v_m$.

The proof of $2$-connectedness is similar.