Graph Duality

# Graph Duality

Definition: For a planar graph $G$, the dual of $G$ denoted $G^*$ is a graph obtained by replacing all faces in $G$ with vertices, and connecting vertices with edges if those faces share an edge. |

For example, let's look at the following graph $G$ and a dual of $G$, $G^*$:

Note that just because two graphs $G$ and $H$ are isomorphic ( $G \cong H$ ), these duals are not necessarily isomorphic. Hence $G \cong H \nRightarrow G^* \cong H^*$

We will now look at some properties of graph duals.

Lemma 1: Suppose that $G$ is a planar graph with $v$ vertices, $e$ edges, and $f$ faces. The dual, of $G$, $G^*$ hence has $f$ vertices, $e$ edges, and $v$ faces. |

- **Proof: In the construction of $G^*$, we know that the dual of $G$ must have precisely $f$ vertices and $e$ edges by definition. We can now apply Euler's formula to get that for the graph $G$ we have $v - e + f = 2$, and that for the dual we get that:

\begin{equation} f - e + f^* = 2 \end{equation}

- We note that the only difference between these two equations is $f^*$ and n. Hence $f^* = n$. $\blacksquare$

## Correspondences of Duals

We will now summarize a list of properties relating planar graphs and their duals.

Planar Graph $G$ | Correspondence in $G^*$ |
---|---|

An edge in $G$ | An edge in $G^*$ |

A face in $G$ | A vertex in $G^*$ |

A vertex in $G$ | A face in $G^*$ |

A cycle of length $k$ in $G$ | A cutset in $G^*$ with $k$ edges |

A cutset of $G$ with $k$ edges | A cycle of length $k$ in $G^*$ |

## Duals of a Dual

Suppose that we have a graph G and find a dual $G^*$. If we then take a dual of $G^*$, then what do we get? It turns out that $G^{**} = G$. This should make sense as essentially we are interchanging planar faces and vertices once again.