= 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>.
Back to article page
