Good Research Paper On Euler’s Polyhedron Formula

We know a roadmap when we see one. However, most of us have not really sat and analyzed the complex mathematics that could be hidden deep inside a simple roadmap. Most of us are not aware of the mathematical definition of a roadmap. A roadmap is a non-empty finite collection of possibly curved line segments in a plane, each consisting of exactly two end points in such a way that if any two pairs of lines were to meet, then they would meet only at the two end points. I have described this very concept as scribbles later in this article. Right! Now what?

Given a roadmap, numerous mathematical questions can be formulated and asked. For instance, one can ask:

Can you trace a route on this map that passes through every street at least once? This is more popularly known as the highway inspector problem.
Can you a trace a route on this map that touches every corner exactly once? This also has a fancy popular name – the travelling salesman problem.
What is the least number of colours needed if you wanted to colour each block in such a way that any two blocks with a common street have two distinct colours?
I have, in this text, answered one of these questions and also tried to break down a simple geometric problem, the geodesic dome. But, before we proceed any further, it is important to understand what we are dealing with. Euler’s Polyhedron Formula forms one of the basic foundations of modern graph theory. This formula is used to answer many of the questions posted above as well as give interesting insights into a number of shapes we encounter everyday. So, what is Euler’s Polyhedron Formula? Well, what is a polyhedron, for that matter? Let’s get right to it.
A polyhedron is a solid in R3 space whose faces are polygons. A polyhedron is defined as convex if a line segment joining any two points within the polygon is contained within the polygon. Alternatively, a convex polyhedron is defined algebraically as the set of solutions to a system of linear inequalities given as
m ≤b
where m is a real s x 3 matrix and b is a real s-vector. Convex polyhedral can be achieved from any random set of points by calculating the convex hull of the points in consideration. Fukuda and Mizukoshi’s method (1991) of vertex enumeration can be applied to directly obtain the different faces of a polyhedron.
An easier way to understand a convex polyhedron is by taking the example of a tetrahedron shown in fig 1. A tetrahedron is a system with s = 4 and m = and b = .

Every complex polyhedron can be depicted on the plane of a sphere by a planar graph connecting 3 points.

Plane graphs are those which are drawn on the surface of a sphere whose edges meet only at the vertices. If P is a convex polyhedron with N number of vertices, E number of edges and F faces, then N-E+F=2

Consider 3 different plane graphs shown in fig 2.

Only in fig 1(a) does the above cited formula seem to work with N = 6 vertices, E = 7 edges and F = 3 faces, giving 6 – 7 + 3 = 2. The graphs drawn on the second sphere (b) have 3 unconnected components, while that on the third sphere (c) has 2. However, it is possible to extend Euler’s formula by relating the number of connected components. This extended Euler’s formula is given as N-E+F=c+1, where c is the number of components that are connected. To go further in detail, if we were to consider all three spheres, we get a graph with 6 components that further extends the already extended formula: N-E+F=s+c where s is the number of spheres. This is a simple method of comprehending where the whole number 2 arrived in the original formula – one connected component drawn on one sphere, ie. s = c = 1.

Proof

For any graph G, consider the dual graph G* which has vertices as the plane faces and whose edges merge dual vertices by crossing edges of G. Now consider a spanning tree T in G which has N vertices andN-1 edges. The remaining number of edges in G are crossed by a spanning tree T* which belongs to G*. This has f vertices and f-1 edges. Every edge of G is present in T or is intercepted by an edge of T*. Thus, E=N-1+ F-1 which when re-arranged gives N-E+F=2. This proof will be explained explicitly later in the paper.
However, it is easily understood that this is a very versatile and interesting theorem and has profound applications in not the physical or mathematical sciences, but also extends to cartography, geography, sports etc. Careful investigations of different solids reveal the versatility of the theorem. For instance, the geodesic dome, which is not just found in chemistry as the Buckminster Fullerene, but is also used as the optimized shape of a soccer ball can be easily understood from this theorem. Thus, it is worth exploring Euler’s Formula to a certain degree and showing how it can be applied to some everyday objects.

Some Basic Polyhedra

Euler’s formula makes it easy to investigate basic Euclidean geometry even though the theorem is more topological in nature. One easy way to understand how the formula works is by applying it to basic geometric figures.

The Cube

Even though not the simplest, this is one of the most familiar examples of a polyhedron shown in figure 3. A cube has 6 flat regions which are the faces. There are 12 line segments between each pair of faces which are the edges and the corners where each edge meets are the vertices and a cube has 8 vertices (Davis).
Thus, for a cube,F= 6, E = 12 and N = 8.

The Octahedron

The name octahedron, which means 8 faces, directly reveals one of the components of Euler’s formula – the number of faces as shown in figure 4. This is an 8 faced polyhedron that appears to be two Egyptian pyramids joined together at their bases (Hitchin).
It is easy to understand the other components of the octahedron by holding it up at one of the vertices. There are 4 triangles at the top half and another 4 in the bottom half giving a total of 8 triangles. In addition to these, there are 4 vertices around the middle and one each on top and below giving a total of 6 vertices. There are 4 edges centred on the solid with 4 each connecting to the top and bottom giving a total of 12 edges. Thus, for an octahedron, F = 8, E = 12 and N = 6.
Interestingly, an octahedron is the dual of a cube. The dual of a convex polyhedron is obtained by putting a vertex of the new (dual) polyhedron in the center of each one face of the first polyhedron and if two faces of the initial polyhedron are joined by an edge, then the vertices in the centers of those faces are joined by an edge in the dual. A property of dual polyhedra is that the dual of the dual is the first polyhedron. The dual of the octahedron is the cube. By the development of the dual each one face in the original relates to a vertex in the dual (the vertex set in the middle of the face), and every vertex in the first compares to a face in the dual.The number of edges in a polyhedron and its dual are constantly equivalent, subsequent to another edge is built for each edge interfacing two appearances in the first, so the counts for the dual are the same as the counts in the first, yet with the number of faces and vertices exchanged.

An Alternate Proof to Euler’s Theorem

Martin Isaacs offered a mathematically beautiful explanation and proof to Euler’s theorem which is will be discussed here (Isaacs 1994). This has a much simpler explanation compared to the earlier proof since it proves a more generalized version of Euler’s theorem. It derives from the concept that any invariant remains conserved as the edges are removed.
Let consider a few scribbles. What are scribbles? Isaacs defined scribbles as any illustration or drawing of possibly curved lines and points such that:
Each line segment (edge) has a vertex at each one end. Note: a line segment must have endpoints: a circle with no points on it is not a substantial piece of a scribble, since it has no endpoints. There is no concern if a segment has the same endpoint at both ends, so a circle with a solitary vertex on it is a substantial bit of a scribble.
When two or more segments intersect, there is a vertex at the crossing that segregates all the crossing edges into pieces.
Figure 5 illustrates a scribble.
The scribble illustrated in figure 5 contains 8 vertices, 10 edges and 4 faces in which the entire exterior is considered to be a single face. Here, N = 8, E = 10, and F = 4, giving the usual F-E+N=2.
As explained in an earlier part of this paper, these scribbles can also be disconnected. Consider figure 6. The scribbles here have 4 components, two of which are vertices. We can define a component as a set of vertices connected by edges. Two components vary if there is no vertex to vertex connection through edges. Consider the scribble in figure 6. Here, there are four components out of which two are single vertices.
In this figure, we have N = 12, E = 11, F = 4 and c = 4, where c is the number of components. Simply put, components are detached pieces of a scribble. It is possible for one component to encompass another which means, for instance, if a circle with one point on it with another point inside the circle would be a scribble that consists of two components, two vertices, two faces, and one edge. By analysing some typical examples, a simple formula can bederived which shows:
N-E+F-c=1
This is merely an extension of Euler’s original formula with c = 1. Additionally, it has the ability to give solidarity to an empty scribble that has N = E = c = 0, but F = 1.

Applications

I have analyzed some places where the Euler’s Polyhedron Formula can be applied and present here two such instances which, to me, are highly significant. These are just two cases of numerous instances such as the highway inspector problem, the travelling salesman problem, the connected roadmap problem, etc. where the theorem can be applied. The cases I present here have been short listed after a lot of consideration based on its application to interdisciplinary fields.

The Geodesic Dome

A very common application to the Euler’s Polyhedron Formula is in understanding the Geodesic Dome. These solids were popularized by Buckminster Fuller and are rigid due to their sole composition of triangles. The usual dome is constructed by taking an icosahedron (the dual of a dodecahedron consisting of 20 faces), diving each triangular face into smaller triangles, and then projecting the inner vertices from the center of the icosahedron to the sphere which inscribes the original icosahedrons (Ëuler’s Formula: Applications”). If there are an odd number of sub-triangles, the resulting figure is cut into half or approximately half and the result is a geodesic dome. I have illustrated how these triangles are divided in figure 7 where I have divided each triangle into 22 = 4, 32 = 9, 42 = 16 corresponding sub-triangles (Hugh 1976).
A dome comprised as a result of 22 = 4 or 32 = 9 sub-triangles are called 2V or 3V domes respectively and are illustrated in figure 8. Careful investigations of these domes show that there are six vertices where 5 edges merge since at every sub-divided there will be six vertices merging and the original icosahedron had 12 vertices. Since just half of these are present in a dome, there are 12/2 = 6 vertices.
It is possible to form an infinite number of figures that resemble spheres from triangles such that every vertex has a degree of 5 or 6. Even though there is an infinite number of possible number of edges for a sphere-like object of degree 6, there are, however, exactly 12 vertices of degree 5. This can easily be proven using Euler’s theorem.
Let N5 and N6 be the number of vertices in a sphere like object of degree 5 and 6 respectively. If all the outgoing edges are counted, then we get 5N5+6N6, but this consideration includes every edge twice. Hence, the total number of edges is half this, ie. (5N5+6N6)/2. The number of triangles adjacent to the edges is also the same 5N5+6N6, but this counts the triangles thrice as each triangle is counted adjacent to its vertices. This gives, F=(5N5+6N6)/3. The total number of vertices for this object is merely N5+N6.
According to Euler’s theorem: n-e+f=2= N5+ N6- 5N5+6N62+5N5+6N63

Solving this equation algebraically, we get

2= N5+ N6- 15N5+18N66+10N5+12N66
2= N5+ N6- 5N56- 6N66
2= N5/6
Or,12= N5, which proves our initial statement.

The Six Colour Theorem

The reason I have picked this particular application is because of the mystery that surrounds this problem. The six colour theorem is a popular mathematical theorem states that for any map that can be drawn on a plane, only four colours are needed to paint the regions (for instance, countries) in such a way that assures that countries sharing a boundary are of different colours (Gonthier 2005). Interestingly, the only proof that exists to this theorem is the output of a computer program that checked thousands of cases. However, this theorem can be easily understood by considering that six colours are sufficient to solve the purpose.
It is easier to understand this concept by reducing the map to a graph. Place a vertex in the interior of any country and draw an edge from there connecting all the vertices on the interiors all countries that share an edge by drawing a line which intercepts the shared edge. This now represents a planar dual of the country map. If each vertex is coloured in a way that no two vertices joined by an edge have the same colour then we obtain valid map colouring. It can be shown that every planar map uses six or fewer colours.
The proof derives from induction on the size of the graph. If the graph has six or lower number of vertices, then this assumption is true. If we know the theorem is true for any graph of size less than n, and for any graph which has n > 6, Euler’s theorem can be applied to show that the graph must have a minimum of one vertex of degree 5 or less. If that vertex along with all the edges deriving out of it is removed, we obtain a graph of size n – 1 which is 6-colourable by the initial hypothesis. If we add the new vertex and all the edges that were just removed, the newly formed vertex have 5 or lower number of neighbours, so that there will be a definite colour available to it that will not conflict with the other remaining 5 or fewer.
Thus, a planar graph of size 6 or greater has a vertex with 5 or lesser neighbours. Using Euler’s theorem, we can show that for a planar interconnected graph with 3 or more vertices, E ≤3V-6. To calculate the average degree of each vertex, all the degrees are added and then divided by the total number of vertices. Since each edge has two endpoints, the average degree D is:
D=n NdegnN=2EN≤23V-6N=6-6N
This number is always smaller than 6 which implies that at least one vertex must have degrees smaller than 6. We need to prove that for any planar graph connected through 3 or more vertices that E ≤3N-6. If the graph contains no cycles then, E=N-1< N. Since N ≥3then 2N-6 ≥0. Adding these inequalities we obtain, E<3N-6 which proves this case.
If, however, the graph does contain cycles, like that shown in figure 9, then all possible sets of edge-face pairs need to be considered where the edges and faces touch.
The figure contains four edges and two faces. Here, all the edges are adjacent to F2, but only E2, E3 and E4 are adjacent to F1. With these, we can form a complete set of edge-face pairs as
S={E1, F2, E2, F2, E3, F2, E4, F2, E2, F1, E3, F1, E4, F1}.
This shows that the set S consists of at least 3F elements giving the inequality S≥3F, where |S| is the number of elements in S.Each edge is in contact with at least two faces and in figure 9, E1 touches just one face, and thusS≤2E. Merging this with the earlier inequality, we get: 3F ≤3E. However, if we multiply Euler’s formula by 3 and substitute for F, we get:
2=N-E+F
6=3N-3E+3F
6≤3N-3E+2E

6≤3N-E

E ≤3N-6
Which is once again the desired result and we prove the six colour theorem.
Conclusions
I have described the Euler’s Polyhedron Formula in explicit detail and have applied different kinds of proofs to give a closer understanding to the theorem. The application of this formula has also been applied to basic geometric shapes that easily prove the formula. I have understood the importance of having a formula that is versatile in its applicability and after carefully assessing a few cases, I have presented two extremely significant cases. One case spreads its wings across numerous disciplines while the other is important from a cartographical perspective. These have been presented in a manner that is simple and easily comprehendible.

References

Fukuda, K., and I. Mizukoshi. "Mathematica package: Vertex enumeration for convex polyhedra and hyperplane arrangements." Version 0.3 Beta, Graduate School of Systems Management, University of Tsukuba, Tokyo (1991).
Davis, Tom. 'Home Page -- Tom Davis'. Geometer.org. N.p., 2015. Web. 28 Jan. 2015.
HITCHIN, NIGEL.'A LECTURE ON THE OCTAHEDRON'. Bull. London Math. Soc. 35.5 (2003): 577-600. Web.
Isaacs, I. Martin. Algebra: a graduate course. Vol. 100.American Mathematical Soc., 1994.
Kenner, Hugh. Geodesic math and how to use it.Univ of California Press, 1976.
Gonthier, Georges. "A computer-checked proof of the four colour theorem." (2005).
1, Math 311.Handout 21.Euler’s Formula: Applications (n.d.): n. pag. CSUN. 12 Nov. 2008. Web. 30 Jan. 2015. <http://www.csun.edu/~ac53971/courses/math311/handout21_euler-bis.pdf>.