edited by
9,206 views
19 votes
19 votes

Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is:

  1. $6$
  2. $8$
  3. $9$
  4. $13$
edited by

3 Answers

Best answer
25 votes
25 votes
$f=e-n+2$ where $f$ denotes number of faces E the number of edges $n$ the number of vertices So $f=19-13+2 = 8$ faces

Correct Answer: $B$
edited by
4 votes
4 votes
f=e-n+(k+1)

f=number of faces,

e=number of edges,

n=number of vertices,

k=number of connected components,

for connected graph k=1,so

f=e-n+(1+1)

f=e-n+2

f=19-13+2

f=8
1 votes
1 votes
Answer will be (b) 8 because

f+v-e = 2 for connected graph

f = 2+6 = 8  

f is the no. of regions or faces

e is the number of edges

v is the number of vertices
Answer:

Related questions

15 votes
15 votes
2 answers
1
gatecse asked Sep 21, 2014
8,227 views
Which one of the following graphs is NOT planar? G1G2G3G4
38 votes
38 votes
4 answers
2
gatecse asked Sep 21, 2014
11,545 views
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is:$1...
13 votes
13 votes
5 answers
3
Arjun asked Feb 18, 2021
8,022 views
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.