1
$\begingroup$

Let $\delta$ denotes the minimum degree of vertex in a graph. For all planar graphs on $n$ vertices with $\delta\geq3$, which of the following is TRUE?

$i)$ In any planar embedding, the number of faces is at least $\frac{n}{2}+2$
$ii)$ In any planar embedding, the number of faces is less than $\frac{n}{2}+2$
$iii)$ There is a planar embedding in which the number of faces is less than $\frac{n}{2}+2$
$iv)$ There is a planar embedding in which the number of faces is at most $\frac{n}{\delta+1}$

Based on the well known inequality for planar graphs $2e\geq3f$ and Euler's formula $n-e+f=2$, it can easily be derived $2n+2f-4\geq3f$ or $2(n-2)\geq f$. But this tells us that the number of faces is at most $2(n-2)$. How can I come up to any one of the options given above?

$\endgroup$

1 Answer 1

1
$\begingroup$

Since $\delta \geq 3$, the number of edges is greater than or equal to $\frac{3n}{2}$. Therefore $f=2+e-n \geq 2+\frac{3n}{2}-n = \frac{n}{2}+2$. Thus (i) is true and (iv) is not true because $\frac{n}{\delta+1} < \frac{n}{2}+2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .