TU Wien:Diskrete Mathematik für Informatik VU (Rubey)/Beispiel22

A graph is planar if there exists a drawing in the plane R2 such that no two edges intersect, except at their vertices. Given such a drawing of a connected planar graph G, the dual G∗ of G (with respect to the drawing) has as vertices the ‘regions’ (or ‘faces’) of the embedding. Two vertices of G∗ are connected by an edge, if and only if the two corresponding regions are separated by an edge. Show that G and G∗ have the same number of spanning trees.

Let $T$ be a spanning tree in a connected plane graph $G$. Let $G^{\ast }$ be the dual graph corresponding to an embedding of $G$ in the plane, and let $T^{\ast }$ be the subgraph of $G^{\ast }$ consisting of the edges of $G^{\ast }$ that correspond to the edges of $G$ not in $T$. We want to prove $T^{\ast }$ is a spanning tree of $G^{\ast }$.

First note that $T$ has $|V(G)|-1$ edges, so $T^{\ast }$ has $|E(G)|-(|V(G)|-1)$ edges. By Euler's formula, there are exactly $2-|V(G)|+|E(G)|$ faces in the embedding of $G$, so $|V(G^{\ast })|=2-|V(G)|+|E(G)|$, and we have that $|E(T^{\ast })|=|V(G^{\ast })|-1$. It remains to show that $T^{\ast }$ is acyclic, since an acyclic subgraph of a graph with 1 fewer edge than the number of vertices in the graph is a spanning tree.

Now suppose $T^{\ast }$ has a cycle $C$. Note that $C$ separates the embedding of $G^{\ast }$ into two connected pieces, each of which contains at least one face of the embedding. But then the faces of $G^{\ast }$ correspond to vertices of $G$, and the edges of $C$ must correspond to an edge cut of $G$. But $T$ does not contain any of the edges in that edge cut, so $T$ cannot be a spanning tree, a contradiction.

Thus $T^{\ast }$ is acylic and $|E(T^{\ast })|=|V(G^{\ast })|-1$, and $T^{\ast }$ is a spanning tree in $G^{\ast }$.

You might want to look into matroid theory. These notions are quite a bit easier to understand in that light. A spanning tree of a graph is a basis in the cycle matroid $M$ for the graph. The complement of basis is a basis in the dual matroid. In other words, the complement of a spanning tree in a planar graph is a spanning tree in the dual graph.

Quelle: https://math.stackexchange.com/questions/764566/spanning-trees-in-planar-dual-graph