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

We interpret the subsets of faces of dimension *i*
as a vector space over the two-element field GF(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 b 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, b(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, b(b(v))=0.
If v is a basis vector, corresponding to a single face of the polytope,
this is true because any
*ridge*(face two dimensions lower than*v*) forms the boundary between two facets of*v*, and is therefore cancelled out in the calculation of b(b(v)). In the special case of the empty face, b(v)=0 already and for any linear map b(0)=0. In the special case of a vertex, b(v) is the empty face and again b(b(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 b(v)=0, then v=b(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 b(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 b(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}, b(v) cannot be zero.

With these preliminaries out of the way we are ready to
begin the proof that
Sum(-1^{i} *f _{i}*)=0.

Let BCancelling the two extra parameters_{i}denote the subspace of V_{i}consisting of those vectors for which b(v)=0. Then the map b 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 itsnullspace(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 givesSum(-1which equals zero, because each term B^{i}f) = Sum(-1_{i}^{i}(dim(B_{i}) + dim(B_{i-1})))_{i}appears twice with opposite signs.

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

Semi-automatically filtered from a common source file. Last update: .