graner@ut-ngp.UTEXAS (Nicolas Graner) (06/15/85)
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 have seen a very technical proof, but the result is so simple and
beautiful that there should be a simple and beautiful proof (i.e.
accessible to non mathematicians). Does anyone know of such a proof?
Also, to what kind of polyhedrons does it apply (convex, connected...) ?
Nic. {ihnp4,seismo,allegra,...}!ut-ngp!graner
*If Murphy's law can go wrong, it won't*jas@duke.UUCP (Jon A. Sjogren) (06/17/85)
It certainly applies to convex polyhedra in space. What others? Maybe the proof gives a clue. Take polyhedron P, and repeat the following steps. A) If there is a vertex that is an end-point of exactly two edges, delete the vertex and consider that those two edges are now just *one* edge. This operation will not change the value of the expression F-E+V. Repeat A until there are no more such vertices. B) A "face" is now defined to be i) an ordinary face, or ii) something abstract which replaces another face in this part. Find a vertex at which 3 or more edges meet. Choose one of the edges G. Two distinct faces meet in G. Delete G and put the two faces together into a single "face". (A face is essentially a particular collection of edges that have no free vertex.) If this step is not possible, then it is because there is a "cycle" of edges on the polyhedron that has no distinct interior and exterior on the polyhedron. ... such as could occur on a torus-like polyhedron). Repeat A. Repeat the above until there is only one vertex and one face, when you have the formula, since you have not changed F-E+V.
bts@mcnc.UUCP (Bruce T. Smith) (06/17/85)
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. _____________________________ Bruce T. Smith, MCNC Microelectronics Center of N.C. decvax!mcnc!bts (USENET) P.O. Box 12889, 3021 Cornwallis Rd. bts.mcnc@CSnet-Relay (others) Research Triangle Park, NC 27709
ian@psuvax1.UUCP (Ian Parberry) (06/17/85)
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. robertj@garfield.UUCP (Robert Janes) (06/19/85)
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
ptb@ukc.UUCP (P.T.Breuer) (06/19/85)
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 have seen a very technical proof, but the result is so simple and >beautiful that there should be a simple and beautiful proof (i.e. >accessible to non mathematicians). Does anyone know of such a proof? >Also, to what kind of polyhedrons does it apply (convex, connected...) ? > >Nic. {ihnp4,seismo,allegra,...}!ut-ngp!graner > >*If Murphy's law can go wrong, it won't* 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.
msb@lsuc.UUCP (Mark Brader) (06/19/85)
The formula applies to concave as well as convex polyhedra, as long as the faces don't intersect (I'm not sure what happens if they do); after all, they are topologically equivalent. What it does not apply to is non-simple polyhedra, that is, those with "tunnels" in them. 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 faces themselves must be polygons, rather than having holes in them. (At least, the above works for one polyhedron I drew, and I remember it being something like that. It was in Martin Gardner's column once upon a time.) Mark Brader
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (06/21/85)
> ... What it does not apply to is non-simple > polyhedra, that is, those with "tunnels" in them. They better be connected, too.
bobm@rtech.UUCP (Bob Mcqueer) (06/24/85)
> ..... 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. Boy, does this discussion take me back a long ways. Bob McQueer ihnp4!amdahl!rtech!bobm
leeper@mtgzz.UUCP (m.r.leeper) (06/24/85)
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
wyant@apollo.uucp (Geoffrey Wyant) (06/27/85)
For an interesting and entertaining discussion on Euler's formula,
read the book "Proofs and Refutations" by Imre Latkos. It's a dialog
on the process of mathematical discovery using the validity of Euler's
formula as its starting point.
Geoff Wyant
--
Geoff Wyant UUCP: ...{yale,uw-beaver,decvax!wanginst}!apollo!wyantcarr@uiucdcs.Uiuc.ARPA (07/02/85)
/* Written 5:35 pm Jun 26, 1985 by wyant@apollo.uucp in uiucdcs:net.math */
For an interesting and entertaining discussion on Euler's formula,
read the book "Proofs and Refutations" by Imre Latkos. It's a dialog
on the process of mathematical discovery using the validity of Euler's
formula as its starting point.
Geoff Wyant
--
Geoff Wyant UUCP: ...{yale,uw-beaver,decvax!wanginst}!apollo!wyant
/* End of text from uiucdcs:net.math */
That should be Lakatos, not Latkos.