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

From VoWi
Jump to navigation Jump to search

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

First note that has edges, so has edges. By Euler's formula, there are exactly faces in the embedding of , so , and we have that . It remains to show that 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 has a cycle . Note that separates the embedding of into two connected pieces, each of which contains at least one face of the embedding. But then the faces of correspond to vertices of , and the edges of must correspond to an edge cut of . But does not contain any of the edges in that edge cut, so cannot be a spanning tree, a contradiction.

Thus is acylic and , and is a spanning tree in .

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 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