Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G…
2012
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to
- A.
3
- B.
4
- C.
5
- D.
6
Attempted by 249 students.
Show answer & explanation
Correct answer: D
Key idea: use Euler's formula for connected planar graphs.
Step 1: Apply Euler's formula v - e + f = 2. With v = 10 and e = 15 we get f = 2 - 10 + 15 = 7 total faces.
Step 2: The number of bounded faces equals total faces minus the unbounded (outer) face: 7 - 1 = 6.
Therefore the number of bounded faces in any planar embedding of the connected graph is 6.
A video solution is available for this question — log in and enroll to watch it.