Exercise 02

Problem 1

Given a (connected) planar graph P = (V; E), prove Euler’s formula: jV j + jF j jEj = 2, where F (resp. E) is the set of faces (resp. edges) of P and jF j (resp. jEj) is the size of F (resp. E).

Hint: Use induction on jV j, or jEj, or jF j.






























1