6
$\begingroup$

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 enter image description here

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.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I understand the first part, but showing that T* is acyclic is where things start to get tricky. I suppose if you could explain to me what it means when you say that the cycle would separate the embedding of G* into two connected pieces. What is the embedding a word for? The total amount of faces? Also thanks for the quick reply, it has pushed me in the right direction! $\endgroup$ – Nicolai Mons Mogensen Apr 22 '14 at 17:33
  • $\begingroup$ Also, the number of edges in G is the same as the number of edges in G*. Using this information, after we find that |E(T∗)|=|V(G∗)|−1 doesnt this automatically prove that we have a tree. since we have n-1 edges, which is the definition of a tree $\endgroup$ – Nicolai Mons Mogensen Apr 22 '14 at 17:59
  • $\begingroup$ Actually, we don't know that $T^*$ is connected. So you need to either prove $T^*$ is connected, or that it is acyclic in order for $T^*$ to be a spanning tree of $G^*$. $\endgroup$ – Perry Elliott-Iverson Apr 22 '14 at 19:10
  • 1
    $\begingroup$ "Embedding" means the drawing of $G^*$ on the plane. A cycle separates the plane into two pieces by the Jordan Curve Theorem. Each of the two parts of the plane contains a face of $G^*$. $\endgroup$ – Perry Elliott-Iverson Apr 22 '14 at 19:15
  • $\begingroup$ I see, thank you for your time, it's greatly appreaciated! $\endgroup$ – Nicolai Mons Mogensen Apr 22 '14 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.