Homology of Graph and Euler formula for Planar graph

Let $G=(V,E)$$G=(V,E)$ be a directed graph. For an edge between vertices $a$$a$ and $b$$b$, we will use the notation $(a,b)$$(a,b)$.

Define $C_0:=\mathbb{Z}(V)$$C_0 := \mathbb{Z}(V)$ as the free abelian group generated by $V$$V$, and $C_1:=\mathbb{Z}(E)$$C_1 := \mathbb{Z}(E)$ as the free abelian group generated by $E$$E$.

For $n\ge 1,C_n=0$$n \geq 1, C_n = 0$. For undirected graphs, we can build the homology over $\mathbb{Z}/2\mathbb{Z}$$\mathbb Z/2\mathbb Z$.

Define the boundary map $d$$d$ as follows:

$$d:C_1\to C_0,\mathrm{\forall }(a,b)\in E,(a,b)\mapsto a-b$$

Hence, we get a chain complex:

$$\dots 0\stackrel{0}{\to }{C}_1\stackrel{d}{\to }{C}_0\stackrel{0}{\to }0$$

Let us consider the elements in $H_1:=\mathrm{Ker}(d)$$H_1 := \mathrm{Ker}(d)$.

It is evident that the basis of $H_1$$H_1$ consists of loops. For example:

$$d[(a,b)+(b,a)]=d(a,b)+d(b,a)=a-b+b-a=0$$

In general:

$$d[(a_1,a_2)+(a_2,a_3)+\dots +(a_n,a_{n+1})+(a_{n+1},a_1)]=0$$

Hence, $\dim H_1$$\dim H_1$ tells us the number of loops in $G$$G$.

Now, let's think about $\begin{array}{c}{H}_0=\frac{C_0}{d{C}_1}\end{array}$$H_0 = \frac{C_0}{dC_1}\\$.

Two vertices $x,y$$x, y$ are equivalent if and only if $x-y\in d{C}_1$$x - y \in dC_1$. That is, there exists a sequence $(x,x_1),(x_1,x_2),\dots ,(x_k,y)\in E$$(x,x_1), (x_1,x_2), \ldots, (x_k,y) \in E$ connecting them.

Thus, $\dim H_0$$\dim H_0$ indicates the number of connected components in the graph.

Moreover, we have:

$$\dim H_0=\dim C_0-\dim d{C}_1=\dim C_0-\dim C_1+\dim H_1=|V|-|E|+\dim H_1$$

Or equivalently:

$$\dim H_0-\dim H_1=|V|-|E|$$

This is the Euler formula! In the Euler formula, the term $F$$F$ (face) includes the exterior of the graph.

Here, $F=\dim H_1+1$$F = \dim H_1 + 1$ and $\dim H_0=C$$\dim H_0 = C$.

Thus, we derive that:

$$C+1=|V|-|E|+F$$

If $G$$G$ is connected, i.e., $C=1$$C=1$​, we obtain:

$$|V|-|E|+F=2$$

It is not hard to see that there are no difference between planar graph and polyhedron. They are just some vertices and edges. Hence the formula also work for polyhedron.

Proposition. There are only $5$$5$ kinds of Platonic solid!

Proof. Suppose each face of this Platonic solid (regular polyhedron) has p edges, and each vertex is connected to q edges. Then:

$$pF=2E=qV$$

Where $p,q\ge 3$$p,q\ge 3$

Hence

$$V=\frac{4p}{4-(p-2)(q-2)}$$

$$E=\frac{2pq}{4-(p-2)(q-2)}$$

$$F=\frac{4q}{4-(p-2)(q-2)}$$

The range of solution are

$$(p-2)(q-2)<4$$

Hence the solution will be

$$(3,3),(3,4),(3,5),(4,3),(5,3)$$

1. Tetrahedron（正四面体）

2. Cube or Hexahedron（正六面体，也称为立方体）

3. Octahedron（正八面体）

4. Dodecahedron（正十二面体）

5. Icosahedron（正二十面体）