The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 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}$
asked in Graph Theory by Veteran (101k points)
edited by | 1.7k views
planar embedding means planar graph

take an example of complete graph of n=4 and n=3

B) , C) , D) will eliminate

Answer will be $\left \lfloor \frac{n}{2} \right \rfloor+2$

2 Answers

+20 votes
Best answer

If  δ 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 deg 3 of each vertex.
From this graph we can say that 3n<=2e.

As per eulers forumla -> n − e + f = 2.

=> e>=3n/2
=> n+f-2>=3n/2
=> f>=3n/2 - n + 2 
=> f>=n/2 + 2 (No of faces atleast (n/2 + 2) )


answered by Active (3.6k points)

how " From this graph we can say that 3n<=2e.  "  ?

by handshaking theorem 

sum of deg( all vertices )  =  2e

how is it <= , please explain 

ok delta is given to be minimum degree with value 3.

minimum degree of a vertex , means it has to be less than the average degree.

therefore , delta <= (2e/n)



Is this the correct Explanation ?
yes it is correct.

in general, if there are |V| vertices and 'd' is the minimum degree then, it is possible that there will be vertices with degree 'd' or more. Now if you consider that all the vertices have degree 'd', then total degree will be less than or equal to |V|.d (as there could be vertices with higher degree)

also we know that in a graph, total degree = 2|e| (e being no. of edges), as each edge contributes 2 in degree.

equting the above results => |V|.d <= 2|e|
+2 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 
answered by Loyal (8.4k points)
In a triangle degree of every vertex is 2.

It should be degree of every face is at least 3.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,440 questions
46,623 answers
57,021 users