Let delta denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with delta >= 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. In any planar embedding, the number of faces is at most n/2 + 2 D. In any planar embedding, the number of faces is more than n/2 + 2

GATE 2014 · Discrete Mathematics · Graph Planarity · medium

Answer: The number of faces is at least n/2 + 2.

1. Lower-bound E using the minimum degree condition: Since delta >= 3 and there are n vertices: sum deg(v) >= 3n. By handshaking: 2E >= 3n, so E >= 3n/2.
2. Apply Euler's formula to lower-bound F: F = E - n + 2 >= 3n/2 - n + 2 = n/2 + 2. So the number of faces is at least n/2 + 2 in any planar embedding.