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 edgeThis 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.econnecting two different faces of G, and remove it;ecan then only appear once in the boundary of each face, so the graph remains connected -- any path involvingecan 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.

Proofs of Euler's Formula.

From the Geometry Junkyard,
computational
and recreational geometry pointers.

David Eppstein,
Theory Group,
ICS,
UC Irvine.

Semi-automatically filtered from a common source file. Last update: .