A "self-dual" proof of Euler's formula.
We talk of a plane graph if a crossless embedding in the plane
of a planar graph is already given and fixed.
Some Notation: e(G) is the number of edges of the graph G.
Theorem: spanning tree duality.
If G is a connected plane graph and G* its dual then
there is a bijection between the sets of spanning trees of G and G*.
Let T and T* be two corresponding spanning trees then e(G) = e(T)+e(T*).
Proof: [Aigner, Ziegler, Proofs from THE BOOK, p57]
Let T \subset E be the edge set of a spanning tree for G, that is, of a
minimal subgraph that connects all the vertices of G. This graph does not
contain a cycle because of the minimality assumption.
We now need the dual graph G* of G: to construct it, put a vertex into the
interior of each face of G, and connect two such vertices of G* by edges
that correspond to common boundary edges between the corresponding faces.
If there are several common boundary edges, then we draw several connecting
edges in the dual graph. (Thus G* may have double edges even if the original
graph G is simple.)
Now consider the collection T* \subset E* of edges in the dual graph that
corresponds to edges in E\T. The edges in T* connect all the faces, since
T does not have a cycle; but also T* does not contain a cycle, since
otherwise it would separate some vertices of G inside the cycle from
vertices outside (and this cannot be, since T is a spanning subgraph,
and the edges of T and of T* do not intersect). Thus T* is a spanning
tree for G*. qed
Theorem: Euler's formula.
If G is a connected plane graph with v vertices, e edges and f faces, then
v - e + f = 2.
Proof: [Aigner, Ziegler, Proofs from THE BOOK, p57]
For every tree T the number of vertices is one larger than the number of
edges. This yields v(G) = v(T) = e(T)+1, while for the corresponding dual
spanning tree T* is yields f(G) = v(G*) = v(T*) = e(T*)+1. Adding both
equations we get v(G) + f(G) = e(T)+1 + e(T*)+1 = e(G) + 2. qed
References:
- Martin Aigner, G"unter M. Ziegler;
Proofs from THE BOOK,
Springer, Berlin, 1998
- Chapter 10: Three applications of Euler's formula.
- - -
From: "Guenter M. Ziegler"
Date: Thu, 3 Jun 1999 08:34:09 +0200 (MET DST)
Subject: Re: Euler's characteristic
I saw this proof on David Eppstein's ``Geometry Junkyard'', where
Fifteen Proofs are given of Euler's formula,
at http://www.ics.uci.edu/~eppstein/junkyard/euler/
the first one of which is the ``interdigitating trees''
proof. According to Eppstein, this proof (first)
appears in Sommerville's ``An Introduction to the Geometry
of N dimensions'' (London, 1929; Dover reprint 1958),
and is there attributed to van Staudt.
However, I have not looked up either of these two sources.
(van Staudt is hard to read -- I've looked at that
long ago for a different topic. Sommerville should be readable.)
Yours sincerely,
G"unter M. Ziegler