= Euler formula for a connected planar graph
{c}
{title2=$n-m+f=2$}
For a finite <connected graph> with at least one <vertex>, embedded as a <plane graph>, let $n$ count <vertices>, $m$ count <edges>, and $f$ count <faces of a plane graph>, including the <outer face>. Then
$$
n-m+f=2.
$$
The hypotheses refer to an actual embedding; regions in a crossing-filled <graph drawing> do not supply its $f$.<Planar Graphs; Bipartite Matching by Albert R. Meyer (6.042J lecture 5f)>[Planar Graphs; Bipartite Matching, slides lec 5f.14–5f.15]{ref}
In the <plane graph> $K_4$ pictured above, three bounded <faces of a plane graph> and the <outer face> give $4-6+4=2$. A square <cycle graph> gives $4-4+2=2$, while the <graph path> $A-B-C$ gives $3-2+1=2$. Changing a crossing into a new <vertex> changes the <graph>: the square-and-diagonals drawing then has five <vertices>, eight <edges>, and five <faces of a plane graph>, giving $5-8+5=2$.
A proof outline deletes <edges> on <graph cycles>. Each deletion preserves the <connected graph> and merges two <faces of a plane graph>, leaving $n-m+f$ unchanged. Eventually a <tree> remains, with $m=n-1$ and $f=1$. Adding the point at infinity identifies the plane picture with a <sphere>; the value two agrees with its <Euler characteristic> and the <cell-count formula for Euler characteristic>.
Back to article page
