Euler's formula (well, there are several, but this is one of them) is a remarkable characterization of bodies in R3. For such an interesting formula, there are remarkably few different proofs. There's the "usual" proof, and also some proofs using abstract nonsense which, quite frankly, I don't understand.
This is not the usual proof that V-E+F=2. The usual one is to prove it for planar graphs, then claim that one may transform any polytope with no holes in it to a planar graph by puncturing one of the faces and stretching it out into the exterior face of the planar graph).
Instead, this proof uses spanning trees. I've only ever seen it in a book by Coxeter, so I might as well attribute it to him.
One final note: neither proof makes it very clear where the fact that the polytope has no holes is used! (The theorem is false for any polytope with holes). Both really rely on your intuition. Real proofs require a disgusting amount of algebraic topology (and arguably merely redefine "hole" in a convenient manner...).
Sketch of proof that V-E+F=2
With any polytope, we may associate 2 graphs:
- A graph whose nodes are the polytope's vertices, and has the same edges as the polytope (2 nodes are connected by an edge if their vertices are connected by that edge).
- A dual graph, whose nodes are the polytope's faces, and has the same edges as the polytope (2 nodes are connected by an edge if that edge separates the 2 faces).
This in itself is quite remarkable, and should be
meditated upon.
Now pick a spanning tree of the (first) graph. This is some subset of the edges. Paint this subset red, and the remaining edges blue. In the dual graph, look at the set of all blue edges not used by this spanning tree. We claim that this set is a spanning tree of the dual graph! (Accordingly, we call it the "dual spanning tree").
To show this, we must show that it contains no cycles, and that the set of faces with these blue edges is indeed connected.
- No cycle can exist:
- Such a cycle would either be the set of all edges emanating from a vertex, or completely surround some vertex. This would mean the original (red) spanning tree doesn't touch that vertex, which is a contradiction to its being spanning.
- Every face must be connected:
- The only way a face can be disconnected is if it is completely surrounded by a red cycle (either directly, or along with some other adjacent faces). But this would mean that the red spanning tree contains a cycle, which is a contradiction to its being a tree.
So the blue edges are spanning because the red edges are a tree, and they're a tree because the red edges are spanning.
Now just note that every edge is either red or blue. Since the number of edges in a tree is 1 less than the number of nodes, we have V-1 red edges and F-1 blue edges. So E=V+F-2, which is what we set out to prove.