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$

1 Answer 1

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.

$\endgroup$
8
  • $\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$ Commented Apr 22, 2014 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$ Commented Apr 22, 2014 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$ Commented Apr 22, 2014 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$ Commented Apr 22, 2014 at 19:15
  • $\begingroup$ I see, thank you for your time, it's greatly appreaciated! $\endgroup$ Commented Apr 22, 2014 at 19:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .