Lesson 4

Lemma. Let \(G(V,E)\) be a planar graph with \(|V| \ge 3\). Then \[|E| \le 3|V|-6 \ .\]

Proof. Without loss of generality, assume that the graph is connected: if it is not, add a few edges to make it connected; this only makes proving an upper bound on the number of edges more challenging. On the one hand, each face of the graph is bounded by at least three edges (here it is crucial that \(|V| \ge 3\)). On the other hand, each edge belongs to one or two faces. Thus, \[3|F| \le |\{(f, e) \colon f \in F,\ e\in E,\ e \in f\}| \le 2|E| \ .\] Therefore, \(|F| \le 2|E|/3\). Then, by Euler's formula, \[|V|-2=|E|-|F| \ge |E|/3 \ .\]◼