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" <ziegler@math.TU-Berlin.DE>
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