Dual Spanning Trees in a Planar Graph

Now planar graphs have a dual, right? Make a vertex for every face and an edge between them if the two faces are adjacent. (Don’t forget the outer face.) Here’s a fun construction: take a spanning tree $T$ in the original graph and consider those edges impassible for the dual – that is, don’t consider the faces adjacent in the dual if the edge between them is in $T$. Call what remains of the dual graph $D$: I claim $D$ is in fact a spanning tree of the dual. This is actually fairly easy to see once you think about it.

$D$ is connected: you would need a cycle in $T$ to cut it – but $T$ is a tree!

$D$ is a tree: if it had a cycle, that would disconnect $T$ – but $T$ is spanning!

Such $T$ and $D$ are called interdigitating trees (they have their fingers between each other) and you can use them to prove the Euler Characteristic formula for planar graphs quite elegantly. Consider a planar graph $G$ and let $v$ be the number of vertices, $e$ the number of edges and $f$ the number of faces. Then Euler says :

$$v - e + f = 2.$$

You would typically prove this inductively, I’d say, but $T$ and $D$ each individually have $e=v-1$ since they’re trees; the faces get involved because the trees are actually dual, so let’s see where this goes.

We cover all vertices of $G$ with $T$, and all faces of $G$ with $D$. The edges of those two trees together make up all the original edges: the edges of the dual spanning tree correspond one-to-one with the primal edges that aren’t in $T$. Therefore:

$$e = (v-1) + (f-1).$$

Rearrange and you get Euler.