This proof was sent to me by Alex Bogomolny, who found it in a Russian translation (1958) of the 7th edition of J. Hadamard's Elementary Geometry (vol 2). It is closely related to the proof by ear decomposition.
The proof is by induction on the number of faces. First of all, you remove one face and prove the formula \(V-E+F=1\) for open polyhedral surfaces. For a single face the formula obviously holds. Assume the formula holds for a smaller than \(F\) number of faces and consider a surface with number of faces equal to \(F\). Pick two vertices on the boundary (left by the removed face) of the surface and connect them by a chain of internal edges. (The existence of such a chain follows by a form of the Jordan curve theorem.) Now cut along this chain. You get two surfaces for which the formula \(V-E+F=1\) holds. For the first let it be \(V_1-E_1+F_1=1\) and for the second \(V_2-E_2+F_2=1\). Assume the chain contains \(L\) edges hence \(L+1\) vertices. It then follows that \(E_1+E_2=E+L\) and \(V_1+V_2=V+L+1\). Of course \(F_1+F_2=F\). Summing (algebraically) up gives the desired result.
One can also use a dual version of the proof, in which an open disk (initially formed by removing a vertex from the polyhedron) is decomposed by finding alternating sequences of edges and faces.
Proofs of Euler's Formula.
From the Geometry Junkyard,
computational
and recreational geometry pointers.
David Eppstein,
Theory Group,
ICS,
UC Irvine.