Exerpts from discussion on Euler's proof of the Euler Formula:
Re: Euler's proof of Euler's formula?
John Conway (conway@math.Princeton.EDU) Thu, 8 Feb 1996 09:04:02 -0500
On Wed, 7 Feb 1996, Andrew Leahy wrote:
> Hello,
> I'm looking for an accessible reference for Euler's proof of the Euler-Descartes
formula f - e + v = 2 for >convex polyhedra. Also, as long as I have
your attention, does anybody know how to use this formula to >prove that
five colors are sufficient to draw a map on the sphere? Reading through
"Mathematics and the >Imagination" I came across the statement
that the proof of this "rests on" Euler's formula.
> Many thanks in advance.
> Andrew Leahy aleahy@knox.edu
>
Do you really MEAN "EULER's proof", or just ANY proof of EULER's
theorem?
Supposing the latter, let me describe the way I taught this here only yesterday
morning: View the vertices as towns, one of which is called "Rome",
the edges as elevated highways (`roads' or `dykes'), and the faces as fields,
except that one is called "the Sea", since it is initially full
of water.
We suppose the barbarians now start to attack the Roman empire as follows.
In the first stage, they successively flood the other fields, each time
by breaking a dyke that separates an unflooded field from an already flooded
one (or the Sea).
After all the fields have been flooded, there can be at most one path from
any town to Rome, because two such paths would contain a circuit, and so
some field would remain unflooded. A town that's at maximal distance from
Rome (as the chariot speeds) can therefore be at the end of only one undestroyed
road (for only one road from it can lead TOWARDS Rome, and so the others
must lead to towns even further from Rome). The barbarians break up this
road, and sack the town now isolated from Rome, and repeat this procedure
until
they have sacked all towns other than Rome.
They have then set up a 1:1 correspondence between two sets:
1) The set of all roads
2) The union of two sets, namely:
a) towns other than Rome
b) fields other than the Sea, since the breaking of each road either flooded
a unique field or isolated a unique town.
Therefore E = (V-1) + (F-1), as desired.
To prove the 5-color theorem, first alter the map by introducing small new
faces where there were vetrtices of valence more than 3:
ie., replace
\ / \ /
\ / \__/
_____\/_____
by
____/ \____
/\ \__/
/ \ / \
/ \ / \
It suffices to show that we can 5-color this new map, since after doing
so, we can let these small faces shrink to points, and so find a 5-coloring
for the original one.
So we only need to show that all trivalent maps can be 5-colored. But for
such a map the Cauchy relations read:
3V = 2E = fF, where f is the average number of sides to a face. {By the
way, this is the reason that I prefer to use the CAPITAL letters V,E,F for
the numbers of vertices, edges, faces.}
[In general the Cauchy relations are vV = 2E = fF, where v;f are the average
number of sides per vertex;face respectively. To prove them, observe that
the total number of edge-ends is vV = 2E, since each edge has 2 ends, while
the average per vertex is v : similarly the total number of edge-sides is
2E = fF.]
Now 12 = 6V - 6E + 6F (from Euler) = 2fF - 3fF + 6F (from Cauchy) = (6-f)F,
whence we see that f < 6.
But since the AVERAGE number of edges per face is less than 6, there must
be SOME face that actually has less than 6 sides. If it's a pentagon P,
surrounded say by other faces A,B,C,D,E in that order, then unless A touches
C we can delete the edges that separate P from these faces to obtain a simpler
map M*.
I forgot to say that the map M we started with was suppose to be a "minimal
criminal" in the mathematicians' slang - that is to say, a non-5-colorable
trivalent map with the smallest possible number of faces.
So M* must be 5-colorable. Restoring the two edges we deleted, we obtain
a 5-coloring of all the faces of M other than our pentagon P, in which A
and C have been assigned the same color, so that
the faces A,B,C,D,E have used at most 4 colors, and we can assign the fifth
to P.
However, if A and C touch, we can't do this, since the `map' M* would then
contain a face that touched itself. But if A and C touch each other, then
B and D can't, and we can work with those instead.
If some face Q has strictly less that 5 sides, the argument is even simpler:
we 5-color the map M* obtained by deleting any ONE of the edges around Q,
then restore that edge, and color Q with one of the colors not assigned
to the faces abutting it.
This is Percy Heawood's proof, which he gave shortly after finding the fallacy
in A.B.Kempe's supposed proof of the 4-color theorem. [The 4-color theorem
was supposed to have been established by Kempe's proof for some quite large
number of years. It was only after Heawood pointed out the fallacy that
the 4-color problem really became notorious.]
I heard lots of anecdotes about Heawood from someone (Professor Gibney
- an emeritus prof of chemistry) who knew him at Durham University, where
in his later years he was renowned as quite a martinet. One was of a garden
party, at which someone remarked to Heawood that his watch was 1 hour 17
minutes slow : "Oh no, no, no, it isn't", said Heawood, "it's
10 hours 43 minutes fast!".
WWR Ball & HSM Coxeter, Mathematical Recreations and Essays (12th ed.)
was in print at least until quite recently with U. of Toronto Press.
A very rich resource!
John Conway
I have a 13th edition from Dover, bought in 1991.
>A very rich resource!
Seconded
Duncan J. Melville
Dept of Mathematics
St. Lawrence University
Canton, NY 13617
dmel@music.stlawu.edu
Concerning references for the Euler's proof of the Euler-Descartes formula,
perhaps a helpful source is the section on historical remarks and comments
plus the biography of the paper by Branko Grunbaum and G.C. Shephard (A
new look at Euler's Theorem for polyhedra) published in the Amer. Math.
Monthly, 101 (1994),109-128. The book "Descartes on Polyhedra: A Study
of De Solidorum Elementis" by P.J.Federico (Springer-Verlag,1982) is
also helpful. (In the historical remark of the paper, it is mentioned that
the credit
bestowed on Descartes may be in doubt.)
About the mathematics of the five colour result, the key point (making use
of the Euler formula) is this : In a simple connected planar graph, there
is a vertex with degree not exceeding 5. In other words, there is a country
touching no more than 5 countries. The explanation goes like this. It is
more convenient to cast the Euler formula in the language of planar graph,
viz. v-e+f = 2, where v is the number of vertices, e is the number of edges
f is the number of faces on the plane partitioned by the edges. We note
that 3f cannot exceed 2e. Suppose there is no vertex of degree less than
6, then 6v does not exceed 2e. By the formula v-e+f = 2, we conclude that
2 cannot exceed e/3 - e +2e/3, which is 0, a contradiction!
Man-Keung Siu
Department of Mathematics
University of Hong Kong
February 8, 1996.
I believe that I first learned the Euler formula--Descares didn't quite
have it--from WHAT IS MATHEMATICS by Courant & Robbins. The account
begins on page 236. They go on to use the formula to show that there are
only five regular solids.
One fine thing about the formula is that it consists of two-dimensional
elements faces; one-dimensional elements, edges; zero-dimensional elements,
vertices.
There is an elegant proof in Harold Scott Macdonald Coxeter's INTRODUCTION
TO GEOMETRY (2nd edition) on page 152 &153. The proof is about 13 lines
long, and it builds up the figures beginning from a single
point, which will soon be a vertex. Coxeter too goes on to use the formula
to demonstrate that there are exactly 5 regular solids.
Of course at the conclusion of the ELEMENTS, Euclid shows that there are
5 regular solids, but his proof is metric & fails for Lobachevski's
non-euclidean geometry. Since Euler's proof depends on counting,it leads
to a proof that there are five regular pseudo-solids. There are no squares
in hyperbolic geometry, but there are pseudo-squares with 4 equal sides
and 4 equal acute angles, and hence pseuso-cubes, etc.
The question as to when the first "formula" was "published"
dealing with combinations or permutations really depends on what is meant
by "formula" anmd d what is meant by "publishing". The
process of calculating n choose k was known in medieval India; examples
are given by Mahavira and Bhaskara at least. The Indian authors described
the process in words in some of their manuscripts, so if that is "publishing
a formula", then that is where the credit is due. Mahavira lived in
the ninth century and Bhaskara in the twelfth. Proofs of these results are
first written down - as far as is known - in early fourteenth century North
Africa, in the work of ibn al-Banna. A somewhat different proof was given
shortly afterwards by Levi ben Gerson, in southern France. Both of these
authors also described the process of calculating permutations of k elements
in a set of n. Levi even gave inductive proofs of his results. The "formulas"
then disappear for a while and reappear in the work of various Ita
lian mathematicians in the Renaissance, including Tartaglia and CArdano.
But even they did not have what we consider "formulas". The more
interesting question, to my mind anyway, is if or whether the information
actually traveled from North Africa through France to Italy, or whether
the Italians rediscovered these results independently.
Main page...
The Math Forum is a research and educational enterprise of the Goodwin College of Professional Studies.