Is the dual of a maximal plane graph with at least three vertices 2-edge-connected?

254 Views Asked by At

Maximal planar graph: a planar graph that is not a spanning subgraph of another planar graph

maximal plane graph: a specific embedding of a maximal planar graph

Is the dual of a maximal plane graph with at least three vertices 2-edge-connected?

I think it can be proved by showing every vertex of the dual graph is 2-connected with the vertex of the outer face of the graph, but I cannot show it clear.

1

There are 1 best solutions below

0
On BEST ANSWER

Take a straight line embedding of the maximal planar graph. By maximality every face is a triangle. To show that it is $2$-connected, take any two faces $F_1$ and $F_2$, and any two points $p$ and $q$ in the interior of $F_1$ and $F_2$ respectively, and consider the line $(pq)$. For almost any choice of $p$ and $q$, this line does not intersect any vertex, and intersect each face on a (possibly empty) segment, except the outer face for which the intersection is the complement of a segment. Hence the intersected faces defines a circuit in the dual graph, containing $F_1$ and $F_2$ (as well as the outer face). As the connectivity between any two faces is at least 2, the graph is 2-connected, hence 2-edge-connected.

This also shows that your intuition is right: we can find two paths from every face to the outer face in the same way.