21 January 2008

Nineteen proofs of Euler's formula

Nineteen proofs of Euler's Formula, from The Geometry Junkyard. (This is the one that says that if V, E, and F are the number of vertices, edges, and faces of a polyhedron, then V-E+F=2.)

This is something of an embarrassment of riches; I want one for my class tomorrow, because we're talking about regular polyhedra, and to talk about that without mentioning Euler's formula would be remiss.

I'll probably give "Proof #8: Sum of angles" from the page, which sums up the various angles involved in a drawing of the graph corresponding to a polyhedron, or the proof that Wikipedia attributes to Cauchy, which triangulates that graph (not changing V-E+F) and then removes edges one or two at a time (still not changing V-E+F). These seem the most accessible. (They're also the ones I managed to struggle in the general direction of while walking to the coffee house a couple hours ago.)

If I wanted to scare the hell out of my students (this class has no prerequisites), I'd give the "binary homology" proof.

12 comments:

John Armstrong said...

For your students, I'd suggest a more heuristic version of the induction on edges argument, because it's really easy to draw the graph getting bigger and bigger as you add new features.

You start with a single vertex (draw a dot on the board) so you can check V-E+F=2. Then you make it bigger by either:
1) adding an edge-vertex spur to the graph, or
2) adding an edge connecting two existing vertices.
The first adds one to V and E, while the second adds one to E and F. Presto.

For you (and the more mathy types who might read this) I'll suggest this exercise, inspired by this post of Terence Tao (and others like it): find the "2-morphisms" between these proofs. That is, each proof is an arrow from hypotheses to conclusion. Find the arrows from one proof to another.

Efrique said...

Thanks very much for this post.

Last week I demonstrated to my six-year-old daughter that for polygons, the number of vertices will always equal the number of edges (V=E).

Then I spent several brief sessions with her where we counted F's, V's and E's on as many polyhedra as we could find to hand. After the first few, I encouraged her to see what happened when she added F+V... she spotted that it was 2 more than E right away.

We eventually checked another dozen or so different ones around the house, including some of my polyhedral dice, counting F+V, predicting E from her guessed formula (E=F+V-2) and seeing that her formula gave the right answer.

It's nice to have a pile of proofs to look at, because I'd like to have some proofs for her when she's ready. I'm bookmarking that.

clem said...

Have you read "Proofs and Refutations" by Imre Lakatos? He discusses his philosophy of dubitability with a sort of seminar whose members offer proofs of that formula, only to be refuted by others who bring up special cases for which the proof is invalid. For example, polygons with holes or nonconvex polyhedra or interpenetrating sides or internal edges, etc. He considers at length the tension between proof strategies that generalize the formula for the special cases and ones that define the special cases out of their notion of 'polyhedron'. The tensions between formalism and mathematical Platonism also come into the discussion.

Isabel said...

Clem,

I have read Lakatos' book; I don't remember it all that well, though, since I read it some years ago. I suspect I'd have a different perspective on the book now, so it may be worth rereading.

Gabe said...

Why only prove it for 3 dimensions when you can generalize it for higher-dimensional convex polytopes? ;)

(I just gave a lecture on the higher-dimensional generalization a few days ago in a graduate student seminar, so I still have it on the brain.)

D. Eppstein said...

Gabe: I'm curious which proof you used for the higher-dimensional generalization. Of the ones I list, #12 (line shelling) would be my choice, but 15-19 also work in any dimension.

Gabe said...

The proof doesn't appear to be on the list; the one I used is from Grunbaum's Convex Polytopes (starting with p130 if anyone has the book). The idea is this:

1) Show that if (n-1)-polytopes satisfy Euler's Theorem, then so do n-prismoids, by recursive enumeration of faces based on the "end polytopes" and a section of the prismoid.
2) Show that if a hyperplane separates a polytope into two pieces and contains precisely one vertex of the polytope, and if the two "half-polytopes" and the section satisfy Euler's Theorem, then so does this polytope.
3) For an arbitrary polytope P, find a hyperplane H such that no translate of it contains more than one vertex of P. Then take translates of H such that each one contains one vertex of P - effectively sectioning P into (V-1) n-prismoids. Each of the prismoids satisfies Euler's Theorem, and we can use step two above to glue them together into pieces that satisfy Euler's Theorem, so the whole piece satisfies Euler's Theorem.

Looking now at the supplementary notes at the end of the chapter - added in the second edition - they call this method the "sweep" method, and then mention Ziegler's shelling proof and make a few more comments on shelling.

Maybe I should chew on some of these other proofs :)

Anonymous said...

Hey are you a professional journalist? This article is very well written, as compared to most other blogs i saw today….
anyhow thanks for the good read!

Anonymous said...

chicago job pharmacy technician pharmacy prescription store
Cymbalta or effexor casino crazy online vegas
http://drdianafisher.com/drdiana/Web/members/rangel-school-of-pharmacy-05/default.aspx best discount free viagra via
reason for blisters on lips anti-smoking
levitra product wellbutrin cause increased anxiety
http://press.nasrecruitment.com/members/viagra-generic-uk-76/default.aspx zoloft gum disease
pfizer zithromax google4534553453322

Anonymous said...

I have found it on this website called [url=http://tipswift.com]tip swift[/url]. You can find it there.
cheers
edit: wrong thread,

Anonymous said...

i have a popup (securityTool) it will not let me run anything, it just keeps popping up and stopping every thing i try to do. i have a anti virus but it tells me all is ok, please help [url=http://gordoarsnaui.com]santoramaa[/url]

levitra said...

Hello friend amazing and very interesting blog about Nineteen proofs of Euler's formula