Euler's Formula, Proof 15: Binary Homology

Portions of the following proof are described by Lakatos (who credits it to Poincaré) however Lakatos omits any detailed justification for the properties of the map $\partial$ defined below, instead treating them as axioms (so the theorem he ends up proving is that that Euler's formula is true of any polyhedron satisfying these axioms, but he doesn't prove that this is true of convex polyhedra).

Like the shelling proof, this proof interprets a polyhedron or polytope as a complex of polyhedral faces of varying dimensions, with $f_{i}$ denoting the number of faces of dimension $i$ . And like that proof, we add two "extra" cells, one for the whole polytope and one for the "empty face", so $f_{- 1} = f_{d} = 1$ .

We interpret the subsets of faces of dimension $i$ as a vector space over the two-element field $Z_{2}$ , with vector addition being performed by symmetric difference of subsets (also known as exclusive or). In this way we get $d + 1$ vector spaces $V_{i}$ , with dimensions equal to $f_{i}$ . The sets of faces of the polytope can be interpreted as forming bases for these vector spaces.

These spaces also come equipped with a linear mapping $\partial$ taking each space $V_{i}$ to the next lower dimensional space, defined on each face to be the set of its facets. When $v$ is a sum of faces, $\partial v$ is the sum of the corresponding sets of facets. (The empty face has no facets, and a vertex is defined to have the empty face as its only facet.) This mapping has two very important properties:

Boundaries have no boundaries. In other words, for any vector $v$ , $\partial \partial v = 0$ . If $v$ is a basis vector, corresponding to a single face of the polytope, this is true because any ridge (a face two dimensions lower than $v$ ) forms the boundary between two facets of $v$ , and is therefore cancelled out in the calculation of $\partial \partial v$ . In the special case of the empty face, $\partial v = 0$ already and for any linear map $\partial 0 = 0$ . In the special case of a vertex, $\partial v$ is the empty face and again $\partial \partial v = 0$ . The result follows as well for vectors other than the bases by linearity.
Any vector without a boundary is itself a boundary. In other words, for any vector $v$ , if $\partial v = 0$ , then $v = \partial w$ for some $w$ . If $v = 0$ then we can choose $w = 0$ as well; for nonzero $v$ we prove this by analyzing the vectors of each dimension separately. If $v$ is in $V_{- 1}$ , it must be the empty face itself and is the boundary of some vertex. If $v$ is in $V_{0}$ , it must consist of an even number of vertices for $\partial v$ to be zero. These vertices can be paired up and connected by paths; then w can be taken to be the vector sum of these paths. If $v$ is in $V_{1}$ , it forms a set of edges meeting an even number of times at each vertex; these edges can be grouped into Jordan curves and $w$ can be taken to be the vector sum of regions bounded by these curves. If $v$ is in $V_{2}$ , it must be the whole set of facets of the polyhedron, since we can find a path on the polyhedron boundary from any facet to any other facet (avoiding vertices), and none of the edges crossed by this path can be in $\partial v$ . So we can take $w$ to be the single cell corresponding to the whole polyhedron. Finally, if $v$ is a nonzero vector in $V_{3}$ , $\partial v$ cannot be zero.

With these preliminaries out of the way we are ready to begin the proof that $\sum_{i = - 1}^{d} (- 1)^{i} f_{i} = 0$ .

Let $B_{i}$ denote the subspace of $V_{i}$ consisting of those vectors for which $\partial v = 0$ . Then the map $\partial$ takes $V_{i}$ to $B_{i - 1}$ . Whenever we have a linear map of vector spaces, we can use it to decompose the original space into its nullspace (the set of vectors mapped to zero, here $B_{i}$ ) and its orthogonal complement, which is mapped one-to-one onto the image of the map. This tells us that $\dim V_{i} = \dim B_{i} + \dim B_{i - 1}$ . Plugging this expansion into the sum we are trying to evaluate gives $\sum_{i = - 1}^{d} (- 1)^{i} f_{i} = \sum_{i = - 1}^{d} (- 1)^{i} (\dim B_{i} + \dim B_{i - 1})$ which equals zero, because each term $B_{i}$ appears twice with opposite signs.

Cancelling the two extra parameters $f_{- 1}$ and $f_{3}$ from the sum gives the usual Euler formula. I suspect there is a more direct, dimensionless way of proving that boundaryless vectors are themselves boundaries, but I don't see it and Lakatos doesn't describe it.

Homology theory, one of the foundation stones of algebraic topology, is devoted to defining similar vector spaces and understanding the extent to which the key equation $\dim V_{i} = \dim B_{i} + \dim B_{i - 1}$ fails to be true in other topological spaces.

Proofs of Euler's Formula.
From the Geometry Junkyard, computational and recreational geometry pointers.
David Eppstein, Theory Group, ICS, UC Irvine.