GATE 2015 CS (CS1) – Question 44
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 ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 24
Explanation
Every face has 3 edges on its boundary and each edge borders two faces, so $3F = 2E$ and $F = \frac{2E}{3}$. Euler's formula $V - E + F = 2$ gives $10 - E + \frac{2E}{3} = 2$, so $\frac{E}{3} = 8$ and $E = 24$.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2017 CS (CS1) Q30
- GATE 2014 CS (CS1) Q61
- GATE 2014 CS (CS1) Q62
- GATE 2014 CS (CS2) Q13
- GATE 2014 CS (CS2) Q61
- GATE 2014 CS (CS3) Q61
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →