The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
2k views

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

asked in Graph Theory by Boss (18.3k points)
retagged by | 2k views
0
Does bounded faces mean cycles?

2 Answers

+24 votes
Best answer

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

answered by Active (2.6k points)
edited by
0

"number of bounded faces = no. of faces -1" is this formula ?

+3

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

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?
answered by (19 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,599 questions
48,599 answers
155,657 comments
63,729 users