This proof is really just a variation on shelling, but is included here for its historical significance: it was used by Cauchy, and was examined at length by Lakatos.
Begin with a convex planar drawing of the polyhedron's edges. If there is a non-triangular face, add a diagonal to a face, dividing it in two and adding one to the numbers of edges and faces; the result then follows by induction.
So suppose we have any planar graph with all interior faces triangular, with at least two such faces, and with the further property that one can get from any interior point to any other by a path that avoids the boundary of the graph's outer face. (The triangulation of the convex drawing of our polyhedron clearly satisfies these properties.) Then there are always at least two triangles having edges on this boundary, such that the removal of either one leaves a single triangle or a smaller graph of the same type; this can be proved by an induction on the number of triangles, for if some boundary triangle disconnects the interior points, the two disconnected components on its two non-boundary edges must either be single triangles (which are removable) or have (by induction) two removable boundary triangles, at least one of which will be removable in the overall graph.
So remove boundary triangles one by one; at each step we remove either one edge and one face, or two edges, a face, and a vertex. In all cases \(V-E+F\) remains unchanged. Eventually we reach a graph formed by a single triangle at which point \(V-E+F=3-3+2=2\).
The case analysis occurring in higher dimensional versions of this proof is closely related to Radon's theorem that any \(d+2\) points can be partitioned into two subsets with intersecting convex hulls, and to "flipping" based algorithms for constructing Delaunay triangulations and convex hulls.
Proofs of Euler's Formula.
From the Geometry Junkyard,
computational
and recreational geometry pointers.
David Eppstein,
Theory Group,
ICS,
UC Irvine.