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 _________.

Comments

The graph if anyone is interested - 

---

v-e+f =2

v+f-1 = e + 1

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

---

#poisionedKheer 😭

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

Here, |V| = 8 and |R| = 5

From Euler equation, for any connected planar graph (Need not to be simple)

|V| + |R| = |E| + 2   always hold true.

 

where,  |V| = Number of vertices     |R| = Number of faces or Regions    |E| = Number of Edges

hence, 8 + 5 = |E| + 2

            |E| = 11

 

Answer 5

r=e-v+2

v=8 & r=5

5=e-8+2

e=5+6=11

Answer 6

we have 8 vertices and they are connected, so they need to have atleast 7 edges
in the simplest case of connectedness all the vertices are in a straight line so we have just one face
 
so we have
7 edges = 1 face
8 edges = 2 faces, where ever you add the edge
9 edges = 3 faces,
and it goes on

so its like no of edges = no of faces + 6
we have no of faces = 5
so 5+6 = 11