GATE2014-3-52

Question

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?

• A. In any planar embedding, the number of faces is at least $\frac{n}{2}+2$
• B. In any planar embedding, the number of faces is less than $\frac{n}{2}+2$
• C. There is a planar embedding in which the number of faces is less than $\frac{n}{2}+2$
• D. There is a planar embedding in which the number of faces is at most $\frac {n}{\delta+1}$

Comments

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$

Answer 1

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=n+f-2

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

Comments

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)

3<=(2e/n)

3n<=2e

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|

Answer 2

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 

Comments

In a triangle degree of every vertex is 2.

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