gate 2012 cs closed

Question

Let G be a simple undirected planar graph on 10 vertices with 15 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) 3 
(B) 4 
(C) 5 
(D) 6

Comments

Apply the $\text{Euler's Theorem i.e. V- E + r = 2 , then subtract 1 to exclude the unbounded face you will get 6 as the Answer.}$

---

is it a formula to find number of bounded faces?

---

The formula for the total number of faces. In any graph, we have only one Unbound face and all other remaining are the bounded faces, so doing "-1" to exclude unbound face.

Answer 1

Euler formula :

n-e+f=2

here n=10, e=15 put the values

we get f =7

even number of faces can be bounded( Here maximum 6 bounded faces are possible)