Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / R / 2 / Solution

Choose a spanning tree of the connected plane graph. A tree with $n$ vertices has $n-1$ edges and one face of a plane graph, so $n-(n-1)+1=2$. Add the remaining drawn edges one at a time. Each joins two existing vertices and closes a cycle in a graph; its interior lies in one current face of a plane graph, splitting that face of a plane graph into two by the Jordan curve theorem. Thus $m$ and $f$ increase together while $n$ stays fixed. The quantity $n-m+f$ remains two, proving Euler formula for a connected planar graph.