The GATE Grind

GATE 2014 CS (CS3) – Question 62

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

Let $\delta$ denote minimum vertex degree. For every planar graph on n vertices with $\delta\ge3$, which is TRUE?

  1. Every planar embedding has at least $n/2+2$ faces.
  2. Every planar embedding has fewer than $n/2+2$ faces.
  3. Some planar embedding has fewer than $n/2+2$ faces.
  4. Some planar embedding has at most $n/(\delta+1)$ faces.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Every planar embedding has at least $n/2+2$ faces.

Explanation

The handshake lemma gives2m≥3n, so m≥3n/2. Euler’s formula for ccomponents is f=1+c−n+m≥1+c+n/2≥n/2+2. Therefore **A** holds for every planar embedding. The outer face is included in f.