GATE CSE 2021 Set 1 | Question: 16

Question

In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.

Answer 1

Given: For a planner graph $G$ 

• Number of vertices $(V)= 8$
• Number of region/faces $(R/f)=5$
• Number of edges $(E)=?$

For any planner graph $V+F=E+2$

$\implies 8+5=E+2$

$\implies E=13-2=11$

$\therefore$ Number of edges in given graph $G$ is $11.$

Ref: Planar_graph

Comments

Thanks @Hira Thakur For the answer #suryavansham #poisonedKheer

Answer 2

Euler’s formula for a planar graph:

V-E+F=2

Where, V=#vertices

E=#edges in graph

F=#faces in graph.

Given:

V=8 F=5

So,8-E+5=2

This implies E=11

Answer 3

If A graph is Planar then no. of Faces = no. of edges – no. of vertices + no. of connected Components + 1

that turns out that

r = e-n+k+1

Given the Graph is connected do, K=1

r= e-n+2

Replace the Values and e becomes 11

Answer 4

r=e-v+2

v=8 & r=5

5=e-8+2

e=5+6=11