Why is a connected planar graph isomorphic to its double dual?

1.3k Views Asked by At

Let $G^*$ be the dual graph of a planar graph $G$ (see wikipedia article). How does one prove that if $G$ is connected then it is isomorphic to $G^{**}$?

1

There are 1 best solutions below

0
On

Notice that each face in $G^*$ is represented by one vertex in $G^{**}$. On the other hand in $G^*$ there's exactly one vertex in each face.

This is the case since one can represent $G^*$ by putting vertex $v^*_f$ of $G^*$ inside the corresponding face $f$ of $G$ and by drawing the edge $e^*$ of $G^*$ corresponding to an edge $e$ of $G$ in such a way that it intersects $e$ exactly once and does not intersect any other edge of $G^*$. Then one can use the Jordan curve theorem.

Now vertices $u,v$ are neighbours in $G$ if and only if the faces $f_u^*,f_v^*$ in $G^*$ that contain $v,u$ are adjoint.

Equivalently, vertices $u^{**},v^{**}$ in $G^{**}$ (that correspond to $f_u^*,f_v^*$) are neighbours.

This means any vertices $u,v$ from $G$ become $u^{**},v^{**}$ in $G^{**}$. Also, any $u,v$ are neighbours in $G$ if and only if $u^{**},v^{**}$ in $G^{**}$ are neighbours as well.

Therefore, $G$ is isomorphic to $G^{**}$.