Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site psuvax1.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!harpo!decvax!genrad!panda!talcott!harvard!seismo!rochester!cmu-cs-pt!cadre!psuvax1!ian
From: ian@psuvax1.UUCP (Ian Parberry)
Newsgroups: net.math
Subject: Re: Euler's(?) formula
Message-ID: <1662@psuvax1.UUCP>
Date: Mon, 17-Jun-85 15:31:19 EDT
Article-I.D.: psuvax1.1662
Posted: Mon Jun 17 15:31:19 1985
Date-Received: Thu, 20-Jun-85 20:46:06 EDT
References: <1832@ut-ngp.UTEXAS>
Reply-To: ian@psuvax1.UUCP (Ian Parberry)
Distribution: net
Organization: Pennsylvania State Univ.
Lines: 28


One of the cutest proofs of Euler's formula that I have seen is the
following, paraphrased from Street and Wallis, "Combinatorial theory:
an Introduction", CBRC, 1977, p. 430.

Theorem 2.  Suppose that a plane representation of a connected planar
simple graph has v vertices, e edges and f faces.  Then
                         v-e+f=2.                                    (1)

Proof.  By induction on e.  It is easy to see that the theorem is true
when e is small: if e=0, then the graph must consist of 1 vertex, which
means f=1; if e=1 or e=2 we have a path with e+1 vertices and one face.
Now assume the theorem is true for all graphs with E or less edges, and
suppose e=E+1.

It may be that the graph is a tree.  In that case, v=e+1 and f=1, so
that v-e+f=e+1-e+1=2.  Otherwise, the graph has a subgraph which is a
cycle.  Select an edge which lies in a cycle.  That edge will lie
separating 2 faces (possibly one being the exterior face).  If such an
edge is deleted, we obtain a graph with one fewer edge and one fewer
faces than the original.  It has E edges so, by induction, equation (1)
is satisfied; in terms of the original graph, v-(e-1)+(f-1) = 2,
and (1) follows.  QED

Combined with theorem 1 ("the graph corresponding to a convex polyhedron
is planar") this gives the result you seek.  Theorem 1 does have a short
proof, which can be found in the above reference or sought out by the
curious.