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
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.