GATE CSE 2012 | Question: 17

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

Does bounded faces mean cycles?

---

What is bounded faces?

---

@Rakesh K @Nisha Bharti , 

Bounded faces means interior faces . 

In any connected planar graph ,  number of exterior faces is 1 

Total number of faces = Total number of interior faces + total number of exterior faces , 

Total number of faces = Total number of interior faces + 1 

Therefore , Total number of interior faces  = Total number of faces – 1

---

Question became more intresting with 7 as option :)

Answer 1

For any planar graph,
$\text{n(no. of vertices) - e(no. of edges) + f(no. of faces) = 2}$

$f = 15 - 10 + 2= 7$
number of bounded faces $= \text{no. of faces -1}$
                                               $= 7 -1=6$
So, the correct answer would be D

Comments

@jugnu1337 you are correct but but they asked faces so by your formula ,

vertices-edge + faces =2

or ,faces=edge-vertices+2

---

Faces = regions
Bounded = interior regions

All graphs graph have 1 exterior region/face

 

---

The first line of the answer should have been " For any connected planar graph" .

The general formula is :

 no. of vertices + no. of faces = no. of edges + no. of components + 1 .

Answer 2

For any planar graph

v-e+r = 2

10-15+r = 2

-5 + r = 2

r= 7

number of bounded faces = no. of faces -1 (​external or unbounded face)

number of bounded faces = 7 – 1 = 6

Answer 3

Number of edges in minimally connected graph: n-1

So, 10-1=9 (edges used to connect all vertices)

Remaining 15-9=6 edges can be used to connect any two vertices and form a bounded face.

So ans - (d) 6

Is this analogy correct?

Answer 4

Apply the Euler formula n-e+f =2

bounded face = f-1