GATE CSE 2015 Set 1 | Question: 54

Question

Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.

Comments

Planarity is in syllabus?

---

@Arjun Sir, although not explicitly mentioned in the syllabus, questions have appeared from planarity recently.

Eg: GATE CSE 2021 Set 1 | Question: 16 - GATE Overflow for GATE CSE

 

---

Possible configuration based upon the given conditions. Edges = 24

Answer 1

A connected planar graph with 10 vertices and 3 edges on each face is known as a triangulation. In general, a triangulation of a planar graph with n vertices will have 3n - 6 edges. Therefore, a triangulation of a planar graph with 10 vertices will have 3 * 10 - 6 = 24 edges.