📂Graph Theory

Proof of Euler's Polyhedron Formula

Overview

Euler’s polyhedron theorem is also called Euler’s characteristic; in graph theory, it is simply referred to as Euler’s formula. Geometrically, it signifies that the relationship between vertices, edges, and faces of a spatial figure follows #vertices-#edges+#faces=2. For instance, considering a cube, it has $8$ vertices, $12$ edges, and $6$ faces, thus $8-12+6=2$ holds.

Theorem ¹

Link Planar graph For $G$, let $n:=|V(G)|$, $m:=|E(G)|$, $f$ represent the number of faces, then $$ n-m+f=2 $$

---

• The regions distinguished on the plane by the drawing of the planar graph are called faces.

Proof

Strategy: There are various approaches, but this post will introduce a proof using elementary graph theory. Applying mathematical induction by cases makes it possible to prove without much difficulty.

---

Case 1. $n=1$

Since $G$ is connected, $m=1$ and there are no faces except for the infinite face, thus $f=1$ holds. Therefore, $1-0+1=2$ is satisfied.

---

Case 2. When $n>1$ and $G$ is a tree graph

Since $G$ is a tree, $m=n-1$ holds, and since it doesn’t include cycles, $f=1$ holds. Therefore, $n-(n-1)+1=2$ is satisfied.

---

Case 3. When $n>1$ and $G$ is not a tree graph

$G$ contains at least one cycle, let’s say one edge in this cycle is $e$. For the new graph $G-e$ obtained by removing that $e$, $$ |V(G-e)|=n \\ |E(G-e)|=m-1 $$ Meanwhile, by removing $e$, which was enclosing the cycle, the two faces bounded by $e$ merge into one. Thus, the number of faces in $G-e$ becomes $f-1$, and $n-(m-1)+(f-1)=n-m-f=2$ holds.

■

Meanwhile, Euler’s polyhedron theorem can be generalized for $k$ components as follows. The theorem above is a particular case for connected graphs, i.e., $k=1$.

Generalization

For a planar graph $G$, let $n:=|V(G)|$, $m:=|E(G)|$, $f$ represent the number of faces, and $k$ represent the number of components, then the following holds. $$ n-m+f=k+1 $$ This is a generalization of Euler’s polyhedron theorem regarding the connectivity of graphs.

See also

Euler’s characteristic in graph theory

Originally, the Euler characteristic is most famous in graph theory, where Euler’s polyhedron theorem or Euler’s formula is a theorem of graph theory stating that for connected planar graphs $\chi = 2$ holds.

Euler’s characteristic in geometry

It is defined as an integer that satisfies the equation of the Gauss-Bonnet theorem.

Euler’s characteristic in algebraic topology

It is defined as the alternating sum of the Betti numbers for each dimension.