Lesson 5

Lemma. In any planar graph, there is a vertex of degree at most five.

Proof. If every vertex of graph \(G(V,E)\) has degree at least six, then the graph has at least \(3|V|\) edges, which contradicts the inequality \(|E| \le 3|V|-6\).◼