Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 GARFIELD 20/11/84; site garfield.UUCP
Path: utzoo!utcsri!garfield!robertj
From: robertj@garfield.UUCP (Robert Janes)
Newsgroups: net.math
Subject: Re: Euler's(?) formula
Message-ID: <3138@garfield.UUCP>
Date: Tue, 18-Jun-85 20:39:22 EDT
Article-I.D.: garfield.3138
Posted: Tue Jun 18 20:39:22 1985
Date-Received: Tue, 18-Jun-85 21:21:58 EDT
References: <1832@ut-ngp.UTEXAS>
Reply-To: robertj@garfield.UUCP (Robert Janes)
Distribution: net
Organization: Memorial U. of Nfld. C.S. Dept., St. John's
Lines: 43
Summary: applies to convex polyhedra/planar graphs

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.
>
>Nic.                      {ihnp4,seismo,allegra,...}!ut-ngp!graner

	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.

					cheers
					Robert Janes