The Geometry Junkyard


Euler's Formula, Proof 4: Induction on Edges

By combining the two previous proofs we get an induction with a much simpler base case.
If the connected planar graph G has no edges, it is an isolated vertex and V+F-E=1+1-0=2. Otherwise, choose any edge e. If e connects two vertices, contract it, reducing V and E by one. Otherwise, it is a Jordan curve and separates two faces; remove it and reduce F and E by one. In either case the result follows by induction.
This is the proof used by van Lint and Wilson. Other variants are possible -- if e connects two vertices and separates two faces, we may choose in various ways whether to delete or contract e.


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: .