GATE CS 2012 Q.17 (CS Q.17): Graph Theory

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

Official answer and solution

Official answer: D
From: Official GATE 2012 answer key

Solution

Apply Euler's formula for connected planar graphs to calculate the total number of faces, and subtract the unbounded face to obtain the number of bounded faces.

For any simple connected planar graph embedded in the plane, Euler's formula states:

V - E + F = 2

where $V$ is the number of vertices, $E$ is the number of edges, and $F$ is the total number of faces.

We are given $V = 10$ vertices and $E = 15$ edges. Substituting these into Euler's formula:

10 - 15 + F = 2 \implies -5 + F = 2 \implies F = 7

The total faces $F$ consist of interior bounded regions plus exactly one exterior unbounded (outer) face:

\text{Total faces } F = \text{Bounded faces} + 1

Therefore:

\text{Bounded faces} = F - 1 = 7 - 1 = 6

Thus, any planar embedding of $G$ has 6 bounded faces.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 17 of 65, printed as CS Q.17
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source