We can prove the formula for all connected planar graphs, by induction on the number of faces of \(G\).
If \(G\) has only one face, it is acyclic (by the Jordan curve theorem) and connected, so it is a tree and \(E=V-1\). Otherwise, choose an edge \(e\) connecting two different faces of \(G\), and remove it; \(e\) can then only appear once in the boundary of each face, so the graph remains connected – any path involving \(e\) can be replaced by a path around the other side of one of the two faces. This removal decreases both the number of faces and edges by one, and the result then holds by induction.
This proof commonly appears in graph theory textbooks (for instance Bondy and Murty) but is my least favorite: it is to my mind unnecessarily complicated and inelegant; the full justification for some of the steps seems to be just as much work as all of the first proof. It doesn't generalize very well, and there are some critical details that textbook authors often omit.
Proofs of Euler's Formula.
From the Geometry Junkyard,
computational
and recreational geometry pointers.
David Eppstein,
Theory Group,
ICS,
UC Irvine.