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:

(1)

\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.