Proving Euler's Polyhedral Formula by Deleting Edges
For a polyhedron , let be the number of vertices, the number of edges, and the number of faces. Then Euler's polyhedral formula of 1752 is .
There are more than a dozen ways to prove this. Here is one such proof.
First, cut apart along enough edges to form a planar net. (The unbounded polygonal area outside the net is a face.) Cutting an edge in this way adds 1 to and 1 to , so does not change.
Next, triangulate the bounded faces. For each edge added, a face is also added, so again does not change.
Now, whenever possible, find an outside triangle (one with two outside edges). Delete the edges, their common vertex, and the triangular face. Yet again does not change.
If it happens that there is no outside triangle, delete any outside edge and its triangular face (make sure the third vertex is not on the outside); once more does not change. After each such step, make sure to see if there are any outside triangles!
At each step at least one edge is taken away, so eventually the process stops, when there is only a triangle or only one edge. In either case (remember to count the unbounded face!), , which must have been true for the original net and for .
Unfortunately, there is no guarantee that one can cut along the edges of a spanning tree of a convex polyhedron and flatten out the faces of the polyhedron into the plane to obtain what is called a "net". In fact, Euler's polyhedral formula holds for non-convex polyhedra and examples are known where cutting along the edges of a spanning tree cannot be carried out to get a "net" without faces overlapping. Some non-convex polyhedra cannot have a net.
The proof in this Demonstration, while suggestive, is not actually correct. In this way it is similar to Cauchy's proof of Euler's polyhedral formula that was not correct but was made so when it was proved by Peter Mani that shellings for 3-polytopes existed. Put together with the shelling theorem, it works. Geoffrey Shephard's conjecture as to whether or not a convex 3-polytope has a net is still open.
The most extensive source of information about folding and unfolding problems is  E. Demaine and J. O'Rourke, Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Cambridge: Cambridge University Press, 2007. They discuss the nature of Shephard's conjecture and evidence for and against it.
Thanks to Joseph Malkevitch for the comments and references.