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

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