This is the introductory note of a sequence of notes dedicated to Euler-Poincaré characteristic. Here, we deal with Euler’s formula from a graph theoritical viewpoint and exhibit several applications including a proof of Pick’s theorem and the classification of Plato’s solids.
We say that a grah is planar if it can be drawn on (or equivalently on ) without edge-crossings. Determining whether a given graph is planar or not is a difficult question in general, and Euler’s formula gives a useful necessary condition:
Theorem: (Euler’s formula) Let be a connected planar graph. Let denote respectively the number of vertices, edges and faces (including the unbounded one) of . Then
Proof. Let be a spanning tree. Let be the dual graph of and be the subgraph of corresponding to the edges of .
Because is connected, is acyclic, and because is acyclic, is connected. Therefore, is a spanning tree. We deduce that
But , and , hence .
Twenty proofs of Euler’s formula (including this one) can be found on Eppstein’s webpage.
Theorem: The complete graph is planar if and only if .
Proof. We may see easily that is planar when , just draw it! Then, because is a subgraph of when , it is sufficient to prove that is not planar. Suppose by contradiction that can be drawn on the plane without edge-crossings.
Let be the corresponding faces, whose boundaries have edges. Notice that is simple, so , and that each edge belongs to two faces, hence
We deduce from Euler’s formula that . But has five vertices and ten edges, so the relation becomes , a contradiction.
Theorem: The complete bipartite graph is planar if and only if or .
Proof. If or , then is planar as shown by the following figure:
Then, since is a subgraph of if and , it is sufficient to prove that is not planar. Suppose by contradiction that can be drawn on the plane without edge-crossings.
Let be the corresponding faces, whose boundaries have edges. Notice that any cycle in has even length, so , and that each edge belongs to two faces, hence
We deduce from Euler’s formula that . But has six vertices and nine edges, so the relation becomes , a contradiction.
Theorem: Petersen’s graph is not planar.
Proof. Suppose by contradiction that Petersen’s graph can be drawn on the plane without edge-crossings and let be the correponding faces. Noticing that the smallest cycle in Petersen’s graph has length five, we deduce that , hence
From Euler’s formula, we deduce that . But Petersen’s graph has ten vertices and fifteen edges, so the relation becomes , a contradiction.
Our proofs are in fact based on the corollary of Euler’s formula stating that a connected planar graph satisfies
where is the length of the smallest cycle in .
In fact, topological graph theory asks more generally whether, given a graph and a space , there exists an embedding . The answer depends widely on the topology of , so it is not surprinsing to notice topological applications of Euler’s formula.
Theorem: and are not homeomorphic.
Proof. We just saw that there is no embedding whereas there is clearly an embedding .
Theorem: and are not homeomorphic.
Proof. We just saw that there is no embedding . However, it is possible to draw on (or on the Möbius band) without edge-crossings, as illustrated by the following figure:
During our proof of Euler’s formula, we implicitely used Jordan curve theorem to state that connectedness and acyclicness are dual; moreover, applying Euler’s formula for a loop gives Jordan curve theorem, so these two theorems are in fact equivalent. Therefore, while the two previous theorems follow easily from Jordan curve theorem, we did not simplify the proofs, but we formulated them as motivating examples of purely topological applications of topological graph theory.
We already gave a proof of Pick’s theorem in a previous note, here is another one based on Euler’s formula. We also use the following lemma, proved in the mentionned note:
Lemma: Let be a polygon. Then contains a diagonal, that is an edge between two vertices lying in the interior of .
Theorem: (Pick) Let be a simple polygon whose vertices are in . Let (resp. ) denote the cardinality of (resp. of ). Then the area of is given by the formula
Proof. According to the previous lemma, we may triangulate . Moreover, if a triangle contains a point of , we may join this point to the three vertices of . Therefore, we may triangulate using triangles intersecting only at their vertices. For example:
Now, it is not difficult to check Pick’s formula for the previous kind of triangles, hence
Let (resp. ) be the number of boundary edges (resp. interior edges) of the triangulation. Noticing that a boundary edge (resp. an interior edge) lies in exactly one (resp. exactly two) triangle(s), we deduce that . Moreover, we clearly have , and . According to Euler’s formula:
Theorem: There exist only five Plato’s solids, namely the tetrahedron, the hexahedron (cube), the octahedron, the dodecahedron and the icosahedron.
Proof. If each vertex has degree and each face is a -gon, then summing the number of edges adjacent to each vertex we get ; summing the number of boundary edges of each face we get . Using Euler’s formula, we deduce the relation
Of course, we necessarily have . But if then , which is in contradiction with the previous relation; therefore, either and necessarily so that , or and for the same reason.
- either and the polyhedron is a tetrahedron,
- or and the polyhedron is a hexahedron (cube),
- or and the polyhedron is a dodecahedron,
- or and the polyhedron is an octahedron,
- or and the polyhedron is an icosahedron.
Theorem: Any map can be coloured so that two adjacent regions have different colors using only six colors.
Proof. First, we prove that a simple planar graph has a vertex of degree at most five. Suppose by contradiction that any vertex has degree at least six. Let denote the number of faces whose boundaries contain exactly edges and let denote the number of vertices of degree . Because our graph is simple,
and because each vertex has degree at least six,
Using Euler’s formula, we deduce , a contradiction.
Now, a map defines a planar graph; let be its dual graph. In particular, is a simple planar graph, and our theorem is equivalent to the fact that the vertices of can be coloured using only six colors so that two adjacent vertices have different colors. We show this by induction on the number of vertices of . For , there is nothing to prove. Otherwise, let be a vertex of degree at most five. Thanks to our induction hypothesis, can be coloured in a good way. Now, we can label by any color that is different from its neighbors; it is possible because has degree at most five and that we use six colors. Finally, is coloured in a good way.
Actually, the theorem is true for four colors only, but the proof is far from being as elementary as the previous one; see four color theorem. An elementary proof for five colors can be found in M. Aigner and G. Ziegler’s book, Proofs from the Book.