Let denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with ≥ 3, which one of the following is TRUE? A) In any planar embedding, the number of faces is at least (n)/(2) + 2 B) In any planar embedding, the number of faces is less than (n)/(2) + 2 C) There is a planar embedding in which the number of faces is less than (n)/(2) + 2 D) There is a planar embedding in which the number of faces is at most (n)/( + 1)

Official answer: A) In any planar embedding, the number of faces is at least (n)/(2) + 2. Explanation: Let G be a planar graph on n vertices with m edges, and let f be the number of faces in a planar embedding of G. By the handshaking lemma, the sum of vertex degrees is equal to 2m: 2m = Σv ∈ V (v) ≥ n · ≥ 3n m ≥ (3n)/(2) By Euler's formula for a planar graph with k connected components: n - m + f = 1 + k ≥ 2 f = m - n + (1 + k) ≥ m - n + 2 Substituting m ≥ (3n)/(2): f ≥ (3n)/(2) - n + 2 = (n)/(2) + 2 Therefore, in any planar embedding, the number of faces is at least (n)/(2) + 2, making option (A) the correct statement.

B) In any planar embedding, the number of faces is less than (n)/(2) + 2

C) There is a planar embedding in which the number of faces is less than (n)/(2) + 2

D) There is a planar embedding in which the number of faces is at most (n)/( + 1)

Graph Theory

GATE CSE 2014 Set 3 · Q52

MCQ2 marksMedium

Time00:00

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?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: A) In any planar embedding, the number of faces is at least (n)/(2) + 2

Graph Theory

Let $G$ be a planar graph on $n$ vertices with $m$ edges, and let $f$ be the number of faces in a planar embedding of $G$ .

By the handshaking lemma, the sum of vertex degrees is equal to $2m$ :

2m = \sum_{v \in V} \deg(v) \ge n \cdot \delta \ge 3n \implies m \ge \frac{3n}{2}

By Euler's formula for a planar graph with $k$ connected components:

n - m + f = 1 + k \ge 2

f = m - n + (1 + k) \ge m - n + 2

Substituting $m \ge \frac{3n}{2}$ :

f \ge \frac{3n}{2} - n + 2 = \frac{n}{2} + 2

Therefore, in any planar embedding, the number of faces is at least $\frac{n}{2} + 2$ , making option (A) the correct statement.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Graph Theory previous year question is Q52 of the GATE CSE 2014 Set 3 paper. Find more GATE CSE PYQs on Graph Theory in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Graph Theory PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Graph Theory in GATE CSE

Graph Theory has 21 GATE CSE PYQs across 14 papers from 2012 to 2026. 6 of them are 2-mark MCQs like this one, and GATE CSE 2014 Set 3 has 2.

How GATE tests Graph Theory

More from GATE CSE 2014 Set 3

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.