A polyhedron with F faces, V vertices and E edges satisfies F + V = E + 2.

There is an intuitive constructive 'proof': Verify that the formula is
true for a trivial 'object'; supposing that any object may be
constructed from this with the addition of vertices, we observe that if
the added vertex splits an edge, then F + (V+1) = (E+1) + 2, else if it
splits a face, then (F+2) + (V+1) = (E+3) + 2.  (Of course, I am
ignoring the holomogy of these 'objects'.)

-- David Harwood <david@cvl.UUCP>

[ Editor: the author first posted the last formula as
"(F+2) + (V+1) = (E+3)" and corrected it in a follow-up; see also
Gregory Rawlins below. ]

----------

There's a nice discussion of Euler's formula in Lakatos' book "Proofs
and Refutations".  It's a book on the philosophy of math, written as a
dialog between a teacher and a group of students.  The discussion
centers on the Euler formula, however.  The students offer various
proofs, discuss the question of what is a polyhedron, etc.

----------

This is not a solution, but a comment on extending Euler's formula.
You state it that F + V = E + 2.

Consider a vertex to be a zero dimensional boundary.
Consider an edge to be a one dimensional boundary.
etc.

For polyhedra in any number of dimensions:
The sum of the number of even-dimensional boundaries always exceeds the
odd-dimensional boundaries by 1.

Take a common cube which has 8 vertices, 12 edges, etc.

Dim     E       O
0       8
1               12
2       6
3               1
sum     14  -   13  =  1

Now join two tetrahedra at one vertex:

Dim     E       O
0       7
1               12
2       8
3               2
sum     15  -   14  =  1

Now try a variation, a two dimensional tear-drop shape has one vertex,
one edge, and encloses one two dimensional space.  2 - 1 = 1.

The generalizes the Euler formula.  The Euler formula assumes that
there is one three-dimensional area enclosed and nothing above three
dimensions.  I think this points to an induction proof of itself and
Euler.  Build up to the an arbitrary figure.  Start with a point.  To
turn it into a line segment add an edge missing one vertex.  That adds
one even-dimenional boundary, a vertex, and one odd dimensional
boundary, the difference remains one.  If you merge two vertices you
lose a vertex and gain two-dimensional space, this again leaves the
difference the same.

-- Mark Leeper  ...ihnp4!mtgzz!leeper

----------

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.

----------

I assume the technical proof you've seen is Poincare's, which
translates the problem into what's now called homology theory.  (The
basic idea being to define vector spaces generated by the faces, edges
and vertices, and consider the kernels and images of the boundary maps
between these spaces.)  I don't know of a simpler, general proof.
There are several proofs which look very plausible and work for
(usually unspecified) special cases.  You can find many of these in a
beautiful book "Proofs and Refutations" by Imre Lakatos.  The book uses
the history of this problem to illustrate Lakatos's ideas on the
philosophy and history of mathematics.  Thoroughly recommended to
mathematicians and interested bystanders alike.

> ...  What it does not apply to is non-simple
> polyhedra, that is, those with "tunnels" in them.

They better be connected, too.

----------

In article <1832@ut-ngp.UTEXAS> graner@ut-ngp.UTEXAS (Nicolas Graner)
writes:
>I think it was Euler who showed that a polyhedron with F faces,
>V vertices and E edges satisfies the relation: F + V = E + 2.

I believe there is one correction to made in that this applies only to
convex polyhedra.

It is also interesting to note that the same formula applies to
(connected) planar graphs if we count the "exterior" as a region (that
is if we replace the word face with the word region).  The proof in
this case is an induction on the number of edges if we consider two
general cases:

        1) graphs which are trees
        2) planar graphs which are not trees

The proof of 1) follows pretty easily, start with a line segment
        V = 2
        R = 1  ( this is F )
        E = 1

        2 + 1 -1 = 2

then take any old tree and delete an edge so as it is still planar you
must also delete a vertex when you do this, the number of regions
remains the same E is reduced by 1 and so is V so the sum is the same.

The proof for 2) is a bit more difficult but follows from noting that
if we delete an edge which bounds two regions we reduce R by 1 and E by
1 and V remains the same.

This is only a sketch of the proof, any introductory graph theory book
would have the whole proof.

Planar = can be drawn with no crossing lines

this is the only way you can have well defined regions.

-- Robert Janes <robertj@garfield.UUCP>

----------

In article <555@cvl.UUCP> david@cvl.UUCP (David Harwood) writes:
>if the added vertex splits an edge, then F + (V+1) = (E+1) + 2, else
>if it splits a face, then (F+2) + (V+1) = (E+3) + 2.

Shouldn't that be (F+1) + (V+2) = (E+3) + 2 ? (assuming that the
"added vertex" is an edge (in the normal sense) which splits a face).

-- Gregory J.E. Rawlins <watmath!watdaisy!gjerawlins>

----------

> .....  Actually I recall that
> there's a simple extension of the formula that even includes those...
> I think F + V = E + 4T + 2 where T is the number of tunnels. .....

The extension of Euler's formula for graphs with simply connected faces
embedded on spheres with n handles is:

V - E + F = 2 - 2N.

There is an intuitive proof of this one about on the level of the
"induction on the number of edges" proof for the original formula which
a couple people have referred to thus far.  The basic idea is that you
use the "simply connected" condition to assure that >= 1 arcs of the
graph run around each handle, then imagine cutting all the handles,
creating new edges and vertices around the circle of the cut.  Then
pull the handles back into the sphere, filling up the empty holes with
new faces.  You added the same number of new vertices and edges around
each cut, and 2N new faces.  The result is a graph on a sphere, for
which the original Euler formula applies.  An illustration of this is
given in a nice little elementary text "Intuitive Concepts in
Elementary Topology", by B. H. Arnold, Prentice-Hall, 1962.

-- Bob McQueer <ihnp4!amdahl!rtech!bobm>