GATE CS 2014 Set 3 Q52 — Graphs: Connectivity, Matching, Colouring

To find the correct statement, we can use the Handshaking Lemma and Euler's formula for planar graphs.

Step 1: Relate Edges and Vertices using Minimum Degree

Let $n$ be the number of vertices, $e$ be the number of edges, and $f$ be the number of faces in a planar embedding of the graph.

By the Handshaking Lemma, the sum of the degrees of all vertices is equal to twice the number of edges:

Since the minimum degree of any vertex is $\delta \geq 3$, we have $\text{deg}(v) \geq 3$ for all $v \in V$. Therefore:

Step 2: Apply Euler's Formula

For any connected planar graph, Euler's formula states:

Substituting the inequality $e \geq \frac{3n}{2}$ into Euler's formula:

Note: If the graph is disconnected with $k$ components, Euler's formula is $n - e + f = 1 + k$. Since $k \geq 1$, we get:

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

Conclusion

• Option A is TRUE.
• Options B and C are false because $f$ cannot be strictly less than $\frac{n}{2} + 2$.
• Option D is false because the number of faces must be at least $\frac{n}{2} + 2$, which is generally larger than $\frac{n}{\delta+1}$.