Use of Euler's Rule.
Copyright (c) Susan Laflin. August 1999.
Euler's theorem relates to a plane graph, and before it can be applied to this problem, the three-dimensional object must be mapped onto a plane graph. This mapping is obtained by imagining the object surrounded by a sphere. The wire-frame image of the object is projected outwards from the centre of the sphere onto its surface, giving a line-drawing of the object. The surface of the sphere, with the line-drawing, is then opened out to form a plane and the resulting line-drawing is the required planar graph.
Mapping a Cylinder.
The above figure shows the plane graph corresponding to a cylinder and the next figure shows a cube and its corresponding plane graph. The plane graph for the cylinder has 3 faces, 3 edges and 2 vertices, while that for the cube has 6 faces, 12 edges and 8 vertices. These both satisfy Euler's Theorem given below.
Mapping a Cube.
Euler's Theorem.
Let G be a connected plane graph. Let v denote the number of vertices, e denote the number of edges and f denote the number of faces. Then
v + f - e = 2
This is fine when the object can be mapped onto a single connected planar graph, but there are many objects for which this is not the case. When this occurs, Euler's Rule must be extended to deal with more complex objects. Let us consider a cube with a tetrahedron removed from one face, which would map onto two connected planar graphs not one. The simplest solution in this case is to insert an extra edge to connect the two graphs. The resulting diagram has 12 vertices, 9 faces and 19 edges and does satisfy Euler's Rule.
The second case is a graph of genus g. This can be drawn without edges crossing on a surface of genus g but not on a surface of genus g-1. The sphere, used for our previous examples, is a surface of genus zero. Examples of surfaces of genus 1 are ring, torus, cup with handle etc. (Loosely speaking objects with one hole through them). This may be easy to remember by means of the comment that a topologist cannot distinguish between his cup of coffee and his ring-doughnut because they are both of genus one.
For such objects, Euler's equation takes the form:
v + f + e = 2 - 2g
The third extension is needed when we come to deal with non-connected graphs of genus greater than zero. If we have M connected graphs, then it is necessary to count the values of v, e and f for each connected graph. Let V=sum(v), F=sum(f) and E=sum(e), and assume that combining the objects creates H holes. Then the final version of Euler's equation takes the form
V + F - E - H = 2( M - G )
or
V + F - E - H - 2M + 2G = 0
When a change is made to the object, it must balence so that
dV + dF - dE - dH -2dM + 2dG = 0
and provided Euler's Rule is satisfied at each stage, the objects so created will be correctly defined.
Example Using Euler's Rule
Stage 1. Create a single graph (M=1) containing a face and a vertex (F=1 and V=1).
Euler's Equation: dV + dF - 2dM = 0.
Stage 2. Add an edge and a vertex (E=1 and V=1).
Euler's Equation: dV - dE = 0.
Stage 3. Add an edge and a vertex twice more (dE=2 and dV=2).
Euler's Equation. dV - dE = 0.
Stage 4. Add and edge and a face. (dE=1 and dF=1).
Euler's Equation. dF - dE = 0.
Stage 5. Add 3 edges, 2 vertices and another face (dE=3, dV=2 and dF =1).
Euler's Equation. dV + dF - dE = 0.
Stage 6. Add a face, a vertex and 2 edges, twice ( dV=2, dE=4 and dF=2).
Euler's Equation: dV + dF - dE = 0.
Stage 7. Finally add an edge and a face, giving the graph for a cube (dE=1 and dF=1).
Euler's Equation: dF - dE = 0.
Any other graphs can be built up in the same way. You may either start from the very begining, as in this case, or start from some known object such as a cube and continue from there. You will note that the number of steps between each check using Euler's Equation varies in the example, and this is also quite acceptable. This means that there may be several different ways of reaching the same result, all of them equally correct, which makes it very difficult to compare objects and say whether they are the same or not.