edited by
9,967 views
26 votes
26 votes

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

  1. $3$
  2. $4$
  3. $5$
  4. $6$
edited by

3 Answers

Best answer
38 votes
38 votes

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

edited by
1 votes
1 votes

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

0 votes
0 votes
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:

Related questions

17 votes
17 votes
2 answers
1
go_editor asked Sep 29, 2014
6,931 views
K4 and Q3 are graphs with the following structures.Which one of the following statements is TRUE in relation to these graphs?K4 is a planar while Q3 is notBoth K4 and Q3 ...
29 votes
29 votes
4 answers
2
Arjun asked Sep 25, 2014
10,971 views
Which of the following graphs is isomorphic to
111 votes
111 votes
9 answers
3
gatecse asked Sep 12, 2014
34,604 views
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to$15$$30$$90$$36...
5 votes
5 votes
2 answers
4
go_editor asked Jul 13, 2016
2,197 views
Two graphs A and B are shown below: Which one of the following statements is true?Both A and B are planarNeither A nor B is planarA is planar and B is notB is planar and ...