GATE CS 2014 Set 3 Q.62 (CS Q.52): Graph Theory

Let $\delta$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $\delta \ge 3$ , which one of the following is TRUE?

In any planar embedding, the number of faces is at least $\frac{n}{2} + 2$

In any planar embedding, the number of faces is less than $\frac{n}{2} + 2$

There is a planar embedding in which the number of faces is less than $\frac{n}{2} + 2$

There is a planar embedding in which the number of faces is at most $\frac{n}{\delta + 1}$

Official answer and solution

Official answer: A
From: Official GATE 2014 answer key

Solution

Apply Euler's formula for planar graphs alongside the handshaking lemma with minimum degree delta >= 3.

Let $G = (V, E)$ be a planar graph on $n$ vertices with $e$ edges and $f$ faces in a planar embedding.
By the Handshaking Lemma:
$2e = \sum_{v \in V} \deg(v) \ge n \cdot \delta.$
Given that minimum degree $\delta \ge 3$ :
$2e \ge 3n \implies e \ge \frac{3n}{2}.$
By Euler's Formula for connected planar graphs:
$n - e + f = 2 \implies f = 2 - n + e.$
(If the graph has multiple connected components $k \ge 1$ , $n - e + f = 1 + k \ge 2$ , so $f \ge 2 - n + e$ holds in all cases).
Substituting $e \ge \frac{3n}{2}$ into the formula:
$f = 2 - n + e \ge 2 - n + \frac{3n}{2} = \frac{n}{2} + 2.$
Therefore, in any planar embedding, the number of faces is at least $\frac{n}{2} + 2$ (option A).

Final answer

Common trap

Reversing the inequality or confusing the face-edge degree relation with vertex degrees.

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

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 3
Question: 62 of 65, printed as CS Q.52
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