Lesson 3

Theorem (Euler's formula). Let \(G\) be a connected planar graph. Then \[|V(G)|-|E(G)|+|F(G)|=2\ .\]

Proof. Induction on the number \(c\) of cycles in \(G\). Base case: if \(c=0\), then \(G\) is a tree (since \(G\) is connected); in this case, \(|F(G)|=1\) (there is one outer face) and \(|E(G)|=|V(G)|-1\).

Step \(c \to (c+1)\): suppose \(G\) has \((c+1)\) cycles. Consider an arbitrary cycle and delete one of its edges. Denote the resulting graph by \(H\). Then \(H\) is still connected and has at most \(c\) cycles, so we can use the induction hypothesis. Clearly, \(|E(H)|=|E(G)|-1\) and \(|F(H)|=|F(G)|-1\): removing a cycle edge merges two faces into one.◼