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^{*}$ be the dual graph corresponding to an embedding of $G$ in the plane, and let $T^{*}$ be the subgraph of $G^{*}$ consisting of the edges of $G^{*}$ that correspond to the edges of $G$ not in $T$. We want to prove $T^{*}$ is a spanning tree of $G^{*}$.

First note that $T$ has $|V(G)|-1$ edges, so $T^{*}$ 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^{*})|=2-|V(G)|+|E(G)|$, and we have that $|E(T^{*})|=|V(G^{*})|-1$. It remains to show that $T^{*}$ 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^{*}$ has a cycle $C$. Note that $C$ separates the embedding of $G^{*}$ into two connected pieces, each of which contains at least one face of the embedding. But then the faces of $G^{*}$ 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^{*}$ is acylic and $|E(T^{*})|=|V(G^{*})|-1$, and $T^{*}$ is a spanning tree in $G^{*}$.

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