Planar Graphs, Minimum Degree & Faces | GATE CS 2014 (Set 3) Question 59

Computer Sciences > GATE 2014 SET-3 > Planar Graphs

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?

In any planar embedding, the number of faces is at least n/2 + 2.

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

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

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

Correct : a

Related Topics