Show that the number of faces in a planar graph drawing with \( n \ge 3 \) vertices is at most:
Without loss of generality, we can consider connected graphs, because adding edges between components does not change the number of vertices or faces (adding more edges can even increase the number of faces).
Now we substitute the estimate \( | E_G | \le 3 | V_G | -6 \) into the Euler’s formula \( | V_G | - | E_G | + s = 2 \) and get \( s \ le 2 | V_G | -4 \).
\( n-2 \) if the graph does not contain any triangle.
By substituting \( | E_G | \le 2 | V_G | -4 \) into \( | V_G | - | E_G | + s = 2 \) we get \( s \le | V_G | - 2 \).