A Proof of Euler's Theorem for Polyhedrons using the Fundamental Theorem of Linear Algebra
In this article I am going to prove Euler’s theorem \(F+V-E=2\) for any normal polyhedron, where F denotes the number of faces of the polyhedron, V the number of vertices, E the number of edges. The proof will utilize the fundamental theorem of linear algebra. The relationship that exists between these two theorems I think is fascinating.
Let us consider a connected graph \(G=(V,E)\) . Let the number of vertices \(|V|=n\) , and the number of edges \(|E|=m\) . In order to introduce the linear algebra, we would like to represent the graph as a matrix.
Let us create an \(m\times n\) matrix \(M\) , each row representing an edge in \(E\) . For each row, each of its element represent a vertex in \(V\) . The edge corresponding to this row connects 2 elements; set one of them to 1, the other to -1 and the rest elements in this row to 0. Thus we obtain a matrix \(M\) which appropriately represents our graph \(G\) .
Now, let’s study the properties of matrix \(M\) . Consider the linear system
\(M x = 0\) , \(x = (x_1, x_2, ..., x_n)\) . We can write \(Mx = 0\) into m equations, each in the form of \(x_i - x_j = 0\) , or \(x_i = x_j\) . Now, since \(G\) is connected, then for each pair of vertices \(i\) , \(j\) , there are several edges connecting them. In other words, there are several equations relating equating \(x_i\) and \(x_j\) . Therefore, these m equations constrains \(x\) all of its components are equal, which means the dimension of the null space (or the nullity) of \(M\) is 1.
Here comes the fundamental theorem of linear algebra: \[n = \text{nullity}(M) + \text{rank}(M)\]
and \[m = \text{nullity}(M^T) + \text{rank}(M)\]
Thus, \(\text{rank}(M) = n - 1\) and \(\text{nullity}(M^T) = m-n+1\) . Now, consider \(M^T x = 0\) . \(\text{nullity}(M^T)\) is the dimension of the space of all its satisfying solutions. If some \(x \in R^m\) is the solution, what does it mean? Imagine that each edge is like some tube (corresponding to the row \(M_i\) ), and \(x_i\) is the amount of water flowing through this tube (so there is as much as \(x_i\) of water entering this tube and as much as \(x_i\) flowing out of it). Adding these tubes together and we get that for each node connected by the tubes, there is neither water accumulated nor drained. The trivial case is that there is no water flowing in any tube, which corresponds to the trivial solution \(x = 0\) . But, if there exists a non-trivial case, then it must hold that each node, if there is water flowing through it, is connected to both the exit of a tube and the entry of another tube. This means, every solution of \(M^T x = 0\) must construct a “circulation” within the edges of the graph. To explain further, \(x\) assigns a flow amount to each of the edges in \(E\) (still using the former analogy); if \(M^T x = 0\) , the flow of water will circulate in a loop, with no vertex accumulating or draining water. Here my explanation seems to be too verbose and a litter obscure; maybe I can improve my explanation later.
Anyhow, we find that each solution of \(M^T x = 0\) corresponds to a circulation in \(E\) (it may be composed of multiple loops). We can now show that each of these circulations can be decomposed into single loops, each around a “hole” in the graph \(G\) . I think the proof is not difficult and I do not want to make my article too verbose, so I just omit the details. It also turns out that these single loops are independent, i.e. each cannot be represented as the composition of other loops. Hence let us make a jump and conclude that the dimension of the null space of \(M^T\) equals the number of holes in the graph.
Then we go back to the previous equation: \(\text{nullity}(M^T) = m-n+1\) . We can now write it into \(\text{#holes} = \text{#edges} - \text{#vertices} + 1,\) for any connected graph. By far we have done all the preparations, there only remains a final step.
Consider any normal polyhedron (abnormal instances include one with a hole in the middle or one that some part of it has zero thickness) with \(F\) faces, \(E\) edges and \(V\) vertices. Remove one of its faces and it becomes a bowl-like object (suppose its body is empty). One can easily imagine that this bowl can be flattened into a 2D graph and recalled that for this graph, \(\text{#holes} = \text{#edges} - \text{#vertices} + 1,\) Now that #holes \(=F - 1\) (since we have just removed a face), #edges \(= E\) , and #vertices \(= V\) , so \(F-1 = E-V+1 \Rightarrow F+V-E=2.\) We have proved one of Euler’s famous theorems.