Let \(\delta\) denote the minimum degree of a vertex in a graph. For all…

GATE · 2014 · CS · Set 3 · Computer Science & IT

1. A.

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

2. B.

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

3. C.

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

4. D.

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

Attempted by 232 students.