The amount of spanning trees in a planar graph G is equal to the amount of spanning trees in the dual graph G*.
I would like to prove this, i know it's true, but i would like to show that it holds for every spanning tree in G that there exist one and only one co spanning tree in G* for the original spanning tree in G.
I made a drawing of the cubegraph that illustrates what i'm trying to prove
Here i have added a vertex inside every mask in G, to create the dual graph G*.
You can clearly see the idea. If you have a spanning tree in G, the co spanning tree is the edges not colored in G. But i would like to prove that this always count.
I have tried with a proof by bijection, but it is not making sense, and i would like someone to explain to me how i would go about this.
Best Answer
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.