The Theorem that Everyone Else Missed – A Short Proof Of Euler’s Formula

Euler’s Characteristic Formula V-E+F = 2

How is it that for thousands of years the best minds in mathematics did not see the fundamental relationship that, in any regular polyhedron, the sum of the vertices and faces minus the edges equals two? Although this question is interesting, no attempt will be made to answer it. Yet the question, merely by being asked, serves to highlight the tremendous stature of Leonard Euler.

Euler worked from first principles, digging into a topic by performing calculations to get a feel for the shape and edges of a problem, then developed conjectures and proofs based on such research. And so, Euler must have tabulated the edges, faces and vertices of shapes such as the platonic solids to thereby notice this relationship. Perhaps it took an almost childlike playfulness to discover this relationship. Yet it is all speculation. The only fact is that Euler did discover that V-E+F=2 where V, E, and F are, respectively, the vertices, edges and faces of a regular polyhedron

I first learned of Euler’s formula in a senior course on graph theory taught by the Polish graph theorist Dr. Siemion Fajtlowicz. Therefore, let me provide a few definitions before offering a compact proof that V-E+F=2 using basic graph theoretical methods.

Definition. A graph consists of a non-empty set of vertices and a set of edges, possibly empty. If an edge E exists, then it will be related to an unordered pair (a,b) of vertices in V. We may write G=(\{V\},\{E\}) to denote the graph.

A graph is finite if both the vertex set and edge set are finite. A graph that is not finite is infinite. The size of a graph is the number of vertices. The order of a graph is the number of edges. All graphs discussed in this article are finite.

Immediately note that if we are given one edge, then there exist two vertices — because an edge must connect to something and that something will always be a vertex. Two vertices are incident if they share a common edge and said to be adjacent. An edge with identical ends is called a loop while an edge with distinct ends is called a link. A graph is simple if it has no loops.

The degree d(v) of a vertex in a graph G is equal to the number of edges in G incident with v where each loop counts as two edges. Thus, a vertex with two edges has degree 2 because the degree of the other two vertices would be one each, and so the sum of the degrees of all the vertices would be 4. From this we have immediately the following two theorems.

Theorem 1. The sum of the degree of the vertices of a graph equals twice the number of edges. That is

\displaystyle \sum\limits_{i/G}{d({{v}_{i}})}=2e

proof. If a graph has no edges, then e=0 and the theorem is true because the sum of the degree of the vertices of a graph with no edges must, by definition, be zero. If a given vertex has an edge, then there must be a second vertex connected to the first vertex by the given edge and so the sum of the degree of the vertexes will be 2, even if the edge were a loop beginning and returning to a single vertex the degree of that vertex due to the loop would still be 2.

Now, each additional edge added to the graph will increase either the degree of the vertex it is connect to and add one additional vertex or else it will add one degree each to two vertices that already exist. Thus, each time an edge is added, the degree count of the vertices increases by 2. Therefore, the sum of the degree of all the vertices will always be simply twice the number of edges present.

Theorem 1.1 The number of vertices in a graph of odd degree is even.

proof. Let {{v}_{1}},{{v}_{2}} be sets of vertices where the {{v}_{1}} is of odd degree and {{v}_{2}} is of even degree. Then, from Theorem 1, we must have that

\sum\limits_{i/G}{d({{v}_{1}})}+\sum\limits_{i/G}{d({{v}_{2}})}=\sum\limits_{i/G}{d(v)}

but we have already established that

\sum\limits_{i/G}{d({{v}_{i}})}=2e

and therefore we must have

\sum\limits_{i/G}{d({{v}_{1}})}+\sum\limits_{i/G}{d({{v}_{2}})}=2e

\sum\limits_{i/G}{d({{v}_{1}})}=2e-\sum\limits_{i/G}{d({{v}_{2}})}

but

\sum\limits_{i/G}{d({{v}_{2}})}=2{{e}_{2}}

so

\sum\limits_{i/G}{d({{v}_{1}})}=2e-2{{e}_{2}}=2(e-{{e}_{2}})=2{{e}_{1}}

is even. Thus, we have that the sum of the vertices in a graph of odd degree is even. Now, we will need the following definitions to proceed.

Definition. A cycle is a closed chain of edges. A connected graph that contains no cycles is a tree.

Definition. A spanning tree of a graph G is one that uses every vertex of G but not all of the edges of G.

Every connected graph G contains a spanning tree T as a subgraph of G.

Definition. A planer graph is one that can be drawn in the plane without crossing any edges.

Definition. A face in the plane consists of both unbounded and bounded regions.

The last definition allows us to say that the number of “faces” of a finite line segment in the plane is 1, but that the number of faces of an infinite line is 2, one for each side that the line divides the plane into, and that the number of faces of a circle in the plane is 2, one corresponding to the inside and the other to the outside of the circle one being the unbounded and the other the bounded region.

Now we are ready to prove Euler’s formula as it may be stated in graph theory.

Theorem 2. If G is a connected planer graph with vertices v, edges e, and faces f, then

\displaystyle v-e+f=2

proof. Let T be a spanning tree of a graph G. Then the number of faces f=1 and the number of edges e= v – 1 is true for the spanning tree T of G and so we have v-(v+1)+(1)=2 and our formula is true. Now, G may be constructed from T by adding edges to T, but each time we do so we are adding a new face to T. Therefore, with the addition of each new edge, e will increase by 1 and f will increase by 1. Therefore, all of these additions cancel out and we have our formula.

Now, a homomorphism exists between polyhedron and graphs in that a connected plane graph can be uniquely associated with a polyhedron by making any face the flat unbounded part of the plane. Therefore, Euler’s formula is true for polyhedron. We can therefore immediately prove:

Theorem 3. Exactly five platonic solids exist.

proof. Let the number of edges and faces be n and the number of edges each vertex is incident to be d. If we multiply nf, we get twice as many edges because each edge belongs to two faces, so nf is the number of faces multiplied by the number of edges on each face. Likewise, with dv each edge is incident to two faces so that we have dv=2e so that we have the equality

nf=2e=dv

or

e=\frac{dv}{2} and f=\frac{dv}{n}

Now, placing these into Euler’s formula, we get

v+\frac{dv}{n}-\frac{dv}{2}=2

or

(2n+2d-dn)v=4n

But both v and n are positive integers and for (2n+2d-dn)v=4n to be true, we must have that

2n+2d-dn>0

or

(n-2)(d-2)<4

and so there are just five possibilities for the values of n and d and each of these corresponds to one of the five platonic solids, so that we have

n=3,d=3 is a tetrahedron
n=3,d=4 is a hexahedron also known as a cube
n=4,d=3 is a octahedron
n=3,d=5 is a dodecahedron
n=5,d=3 is a icosahedron

the 5 Platonic Solids

QED.

© 2012 Kurt Lovelace – All Rights Reserved