edited by
8,013 views
19 votes
19 votes

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

  1. In any planar embedding, the number of faces is at least $\frac{n}{2}+2$
  2. In any planar embedding, the number of faces is less than $\frac{n}{2}+2$
  3. There is a planar embedding in which the number of faces is less than $\frac{n}{2}+2$
  4. There is a planar embedding in which the number of faces is at most $\frac {n}{\delta+1}$
edited by

2 Answers

Best answer
35 votes
35 votes

If $\delta$ is the minimum degree, given as $3.$ 
Take a vertex of degree $3.$ This vertex has $3$ edges incident to it.
These $3$ edges further lead to $3$ more vertices. Now these vertices can have a minimum degree of $3.$
We get the following planar graph$.$

 

This is the planar graph with minimum degree $3$ for each vertex.
From this graph, we can say that $3n\leq 2e \qquad \to(1)$

As per Euler's formla $: n − e + f = 2 \implies e=n+f-2 \qquad \to (2)$

From $(1)$ and $(2)$
$ n+f-2\geq \frac{3n}{2}$
$\implies f\geq \frac{3n}{2} - n + 2$ 
$\implies f\geq \frac{n}{2} + 2 $   $\text{(No of faces is at-least $(\frac{n}{2} + 2)$ )}$

11 votes
11 votes
Euler's formula for planar graphs:

v − e + f = 2.

v => Number of vertices
e => Number of edges
f => Number of faces

Since degree of every vertex is at least 3, 
below is true from handshaking lemma (Sum of
degrees is twice the number of edges)

3v >= 2e
3v/2 >= e

Putting these values in Euler's formula.
v - 3v/2 + f >= 2

f >= v/2 + 2 
Answer:

Related questions

57 votes
57 votes
11 answers
1
go_editor asked Sep 28, 2014
18,179 views
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?$\left\lfloor\frac {n}{k}\right\rfloor$$\left\lceil \frac{n}{k} \right\r...
32 votes
32 votes
9 answers
2
makhdoom ghaya asked Feb 13, 2015
24,371 views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
31 votes
31 votes
4 answers
3
makhdoom ghaya asked Nov 27, 2016
7,721 views
Which of the following graphs is/are planar?