Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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