Let G be a simple undirected planar graph on n vertices with e edges. If G is a connected graph, then the number of boun...

Question

Let G be a simple undirected planar graph on n vertices with e edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to
A. e - n + 1
B. e + n - 1
C. e - n + 2
D. e + n - 2

Accepted Answer

The number of bounded faces = e - n + 1. Euler's formula for a connected planar graph says V - E + F = 2, where F counts all faces including the one unbounded outer face. So the total number of faces F = E - V + 2 = e - n + 2. The number of bounded faces is F minus 1 (subtracting the unbounded face), giving e - n + 2 - 1 = e - n + 1. This is a direct application of Euler's formula.

Let G be a simple undirected planar graph on n vertices with e edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to A. e - n + 1 B. e + n - 1 C. e - n + 2 D. e + n - 2