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 \mathbb{R}^2 (or equivalently on \mathbb{S}^2) 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 \Gamma \subset \mathbb{R}^2 be a connected planar graph. Let v,e,f denote respectively the number of vertices, edges and faces (including the unbounded one) of \Gamma. Then

v-e+f=2.

Proof. Let T \subset \Gamma be a spanning tree. Let \Gamma^* be the dual graph of \Gamma and T^* be the subgraph of \Gamma^* corresponding to the edges of \Gamma \backslash T.

EulerFormula

Because T is connected, T^* is acyclic, and because T is acyclic, T^* is connected. Therefore, T^* is a spanning tree. We deduce that

\left\{ \begin{array}{l} v(T)-e(T)=1 \\ v(T^*)-v(T^*)=1 \end{array} \right. \Rightarrow v(T) -e(T)-e(T^*) +v(T^*)=2.

But v(T)=v, v(T^*)=v(\Gamma^*)=f and e(T)+e(T^*)=e, hence v-e+f=2. \square

Twenty proofs of Euler’s formula (including this one) can be found on Eppstein’s webpage.

Theorem: The complete graph K_n is planar if and only if n \in \{0,1,2,3,4 \}.

Proof. We may see easily that K_n is planar when 0 \leq n \leq 4, just draw it! Then, because K_n is a subgraph of K_m when n \leq m, it is sufficient to prove that K_5 is not planar. Suppose by contradiction that K_5 can be drawn on the plane without edge-crossings.

Let f_i be the corresponding faces, whose boundaries have n(f_i) edges. Notice that K_5 is simple, so n(f_i) \geq 3, and that each edge belongs to two faces, hence

\displaystyle 2e= \sum\limits_i n(f_i) \geq 3f.

We deduce from Euler’s formula that 2=v-e+ f \leq v- \frac{1}{3}e. But K_5 has five vertices and ten edges, so the relation becomes 6 \leq 5, a contradiction. \square

Theorem: The complete bipartite graph K_{m,n} is planar if and only if m or n \leq 2.

Proof. If m \leq 2 or n \leq 2, then K_{m,n} is planar as shown by the following figure:

PlanarGraphs

Then, since K_{m,n} is a subgraph of K_{p,q} if m \leq p and n \leq q, it is sufficient to prove that K_{3,3} is not planar. Suppose by contradiction that K_{3,3} can be drawn on the plane without edge-crossings.

Let f_i be the corresponding faces, whose boundaries have n(f_i) edges. Notice that any cycle in K_{3,3} has even length, so n(f_i) \geq 4, and that each edge belongs to two faces, hence

\displaystyle 2e= \sum\limits_i n(f_i) \geq 4f.

We deduce from Euler’s formula that 2=v-e+f \leq v- \frac{1}{2}e. But K_{3,3} has six vertices and nine edges, so the relation becomes 4 \leq 3, a contradiction. \square

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 f_i be the correponding faces. Noticing that the smallest cycle in Petersen’s graph has length five, we deduce that n(f_i) \geq 5, hence

\displaystyle 2e= \sum\limits_i n(f_i) \geq 5f.

From Euler’s formula, we deduce that 2=v-e+f \leq v- \frac{3}{5}e. But Petersen’s graph has ten vertices and fifteen edges, so the relation becomes 2 \leq 1, a contradiction. \square

Our proofs are in fact based on the corollary of Euler’s formula stating that a connected planar graph \Gamma satisfies

\displaystyle 2 \leq v- \frac{\ell-2}{\ell} e

where \ell is the length of the smallest cycle in \Gamma.

In fact, topological graph theory asks more generally whether, given a graph \Gamma and a space X, there exists an embedding \Gamma \hookrightarrow X. The answer depends widely on the topology of X, so it is not surprinsing to notice topological applications of Euler’s formula.

Theorem: \mathbb{R}^2 and \mathbb{R}^3 are not homeomorphic.

Proof. We just saw that there is no embedding K_5 \hookrightarrow \mathbb{R}^2 whereas there is clearly an embedding K_5 \hookrightarrow \mathbb{R}^3. \square

Theorem: \mathbb{S}^2 and \mathbb{R}P^2 are not homeomorphic.

Proof. We just saw that there is no embedding K_5 \hookrightarrow \mathbb{R}^2. However, it is possible to draw K_5 on \mathbb{R}P^2 (or on the Möbius band) without edge-crossings, as illustrated by the following figure:

ProjectivePlane\square

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 P \subset \mathbb{R}^2 be a polygon. Then P contains a diagonal, that is an edge between two vertices lying in the interior of P.

Theorem: (Pick) Let P \subset \mathbb{R}^2 be a simple polygon whose vertices are in \mathbb{Z}^2. Let i (resp. b) denote the cardinality of \mathrm{int}(P) \cap \mathbb{Z}^2 (resp. of \partial P \cap \mathbb{Z}^2). Then the area A(P) of P is given by the formula

\displaystyle A(P)= i + \frac{b}{2}-1.

Proof. According to the previous lemma, we may triangulate P. Moreover, if a triangle T contains a point of \mathbb{Z}^2, we may join this point to the three vertices of T. Therefore, we may triangulate P using triangles intersecting \mathbb{Z}^2 only at their vertices. For example:

PickTheorem

Now, it is not difficult to check Pick’s formula for the previous kind of triangles, hence

A(P)= \frac{1}{2}(f-1).

Let e_b (resp. e_i) 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 3(f-1)=2e_b+e_i. Moreover, we clearly have e_b=b, e=e_i+e_b and v=i+b. According to Euler’s formula:

2 = v-e+f = v - (e_i+e_b) + \left( \frac{2}{3} e_i+ \frac{1}{3} e_b + 1 \right) =v- \frac{1}{3} e_i - \frac{2}{3} e_b +1 \\ \\ 2= (i+b) - \frac{1}{3} \left( 3 A(P) - \frac{1}{2} b \right) - \frac{2}{3} b +1 = i- A(P) + \frac{1}{2} b+1

hence A(P)=i + \frac{1}{2}b-1. \square

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 m and each face is a n-gon, then summing the number of edges adjacent to each vertex we get 2e=mv; summing the number of boundary edges of each face we get 2e=nf. Using Euler’s formula, we deduce the relation

\displaystyle \frac{1}{m} + \frac{1}{n} = \frac{1}{2} + \frac{1}{e}.

Of course, we necessarily have m,n \geq 3. But if m,n \geq 4 then \frac{1}{n}+ \frac{1}{m} \leq \frac{1}{2}, which is in contradiction with the previous relation; therefore, either m=3 and necessarily n \in \{ 3,4,5 \} so that \frac{1}{n}+ \frac{1}{m} > \frac{1}{2}, or n=3 and m \in \{3,4,5\} for the same reason.

Consequently, (m,n,e) is:

  • either (3,3,6) and the polyhedron is a tetrahedron,
  • or (3,4,12) and the polyhedron is a hexahedron (cube),
  • or (3,5,30) and the polyhedron is a dodecahedron,
  • or (4,3,12) and the polyhedron is an octahedron,
  • or (5,3,30) and the polyhedron is an icosahedron. \square

PlatonicSolids

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 f_k denote the number of faces whose boundaries contain exactly k edges and let v_k denote the number of vertices of degree k. Because our graph is simple,

\left\{ \begin{array}{l} f=f_3+f_4+ \cdots \\ 2e= 3f_3+4f_4+ \cdots \end{array} \right. \Rightarrow 2e \geq 3(f_3+f_4+ \cdots)=3f,

and because each vertex has degree at least six,

\left\{ \begin{array}{l} v=v_6+v_7+ \cdots \\ 2e= 6v_6+7v_7+ \cdots \end{array} \right. \Rightarrow 2e \geq 6(v_6+v_7+ \cdots) = 2v.

Using Euler’s formula, we deduce 2 =v-e+f \leq \frac{1}{3}e- e + \frac{2}{3}e=0, a contradiction.

Now, a map defines a planar graph; let \Gamma be its dual graph. In particular, \Gamma is a simple planar graph, and our theorem is equivalent to the fact that the vertices of \Gamma can be coloured using only six colors so that two adjacent vertices have different colors. We show this by induction on the number n of vertices of \Gamma. For n\leq 6, there is nothing to prove. Otherwise, let v be a vertex of degree at most five. Thanks to our induction hypothesis, \Gamma \backslash \{v\} can be coloured in a good way. Now, we can label v by any color that is different from its neighbors; it is possible because v has degree at most five and that we use six colors. Finally, \Gamma is coloured in a good way. \square

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.

Advertisements