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$.

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:

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:

$\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:

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$

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.