GATE CSE 2003 | Question: 40

Question

A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid  - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-degree of $G$ cannot be 

• A. $3$
• B. $4$
• C. $5$
• D. $6$

Comments

What about k33 it is also fails the face contain cycle of three ? Answer should be A.

---

By handshaking lemma :

let K be the min degree of vertices then  $k*\left | V \right | < = 2 * |E|$

putting $ |E| <= 3 |V| -6$ we get

$|V| <= \frac{-12}{(k-6)}$

Hence putting option D ie 6 is not possible :)

---

According to the handshaking lemma,we have–

Sum of degree of all vertices =2* |E|

⇒Sum of min-degree of all vertices ≤ 2 *|E| (If we replace degree by min-degree) …i)

⇒Sum of avg-degree of all vertices =2 *|E| (If we replace degree by avg-degree)  ….ii)

⇒Sum of max-degree of all vertices  $\geq$2 *|E| (If we replace degree by max-degree)  …iii)

We need eqn i) in this question.

Sum of min-degree of all vertices ≤ 2 *|E| (If we replace degree by min-degree) 

(Sum of min-degree of all vertices)/2 ≤ |E| 

⇒(Min-degree * V)/2 ≤ |E|                  ⇒(Min-degree * V)/2 ≤ 3|V|-6[given condition]

⇒ (6*V)/2≤ 3|V|-6   ⇒ 3*V/2≤ 3|V|-6    ⇒ 0≤ -6 which is false 

Hence correct answer is option D.

Answer 1

Say every vertex has a minimum degree, therefore, least number of edges that will be in the graph is given by the handshaking lemma as $\frac{min \times |v|}{2}$

But the maximum number of edges for such a graph is defined in the question as $3\times |v| - 6$

Putting the minimum number of edges obtained by handshaking lemma in the given inequality, we get:

$\frac{min \times |v|}{2} \leq 3\times |v| - 6$

$\quad \frac{6 \times |v|}{2} \leq 3\times |v| - 6\text{; putting min degree as 6}$

$\;3 \times |v| \leq 3\times |v| - 6$

$\qquad\;\;0 \leq - 6 $

which is definitely inconsistent.

Hence, answer = option (D)

Comments

$|E|\leq 3\left | v \right |-6$ is formula for planar graph

Now, we can draw planar graph with degree $3$

but cannot draw planar graph with degree $4$,$5$,$6$

So, all three option is correct

what is wrong in this approach?

---

@srestha mam

The formula which you gave is necessary condition of planar graphs but not sufficient condition

means every planar graph is should satisfy the condition, but it doesn't mean which graph is satisfied this condition necessarily to be the planar graph.

The sufficient condition is

A graph is planar if and only if it does not contain a subdivision of K₅ and K_3,3 as a subgraph.

for more details http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/planarity.htm

---

ok

but how option B) and C) satisfying $\left | E \right |\leq 3v-6$ condition?

---

mam, did you mean for this question or your question?

---

this question

Say every vertex has degree 5

So, no of vertices=6

then , no of edges $\binom{6}{2}=15$

$15\leq 18-6$ which is not correct

So, it also satisfying answer

---

mam, read the question carefully.

A graph G=(V,E) satisfies |E|≤3|V|−6.

it means, the graph already satisfies the condition ( Avoid the graphs which doesn't satisfy, means n should be grater than what you taken ) , then what is minimum degree ?

---

I am not getting

Can u draw such a graph?

See, in ans, they use formula for handshaking lemma

which is nothing but a complete graph

right?

---

given that e ≤ 3 n - 6 ,

we know that e ≥ $\frac{min.deg\;\;  n}{2}$

===> $\frac{min.deg\;\;  n}{2}$ ≤ 3 n - 6 , ====> min.deg . n ≤ 6 n - 12

by keeping min.degree = 5 ===> 5 n ≤ 6 n - 12 ===> 12 ≤ 6 n - 5 n ===> n ≥ 12

take n ≥ 12, check the condition.

 

See, in ans, they use formula for handshaking lemma

which is nothing but a complete graph

hand shaking lemma says, 2 |E| = sum of deg of each vertex

2 | E | = k. | N |, let assume all vertices have same degrees = k

===> | E | = $\frac{k\;\; | N |}{2}$

if k is the minimum degree, then Edges may increase in the graph.

===> | E | ≥ $\frac{k\;\; | N |}{2}$

But Complete graph forcing that k should be equal to n-1.

---

ok, yes thanks :)

but there is no direct formula of this $e\geq \frac{min degree(n)}{2}$

but until we assume it, we cannot solve this question

---

but there is no direct formula of this

mam, what it means? i derived it also in my last comment.

---

$\frac{min (deg)}{2}$ is there any formula like this?

we came to this formula from $2\left | E \right |=$ summation of degree of all vertices

from this

right?

that is what I mean

---

the numerator is multiplication of minimum degree with n.

---

 is there any formula like this?

@srestha For this example we have to work with average.

We know $min value\leqslant average \leqslant max value$

Hence $min value \leqslant 2\left | E \right |/\left | V \right |$ (Average degree per vertex) 

When we solve this equation using given values, you will get the answer.

---

What if options are not given?

Then how to approach such problems @Shaik Masthan Sir?

---

generally, if k is degree of each vertices, then we can conclude k.V = 2 |E|

if k is minimum degree, then edges may be increases

∴ k.V ≤ 2.|E| ===> $\frac{k.V}{2}$ ≤ |E|

given that |E| ≤ ( 3 V - 6 )

==> $\frac{k.V}{2}$ ≤ ( 3 V - 6 )

k . V ≤ 6V - 12

k ≤ 6 - $\frac{12}{V}$

k ≤ 5.9999999

k must be not grater than or equal to 6

---

Please explain this:

if k is minimum degree, then edges must be increased

---

it's a typo !

---

What will be the planar graph with min degree 5 ? please draw and upload it or give a reference link.

@Shaik Masthan

---

@Satbir planar graph with min degree 4 and 5-

---

thanks

---

@srestha mam,

@Shaik Masthan sir,

@Satbir sir

for proving purpose in a first go, i had done same stuff However we know,

this is a planar graph property, |E| <= 3|V| - 6 and due to this property we know that in a planar Graph degree of a vertex not exceeds from 5.

So knowing this property we can directly give answer, isn't it ?

Reference : kamla Kirthivasan mam Lecture on Planar Graph.

 

---

we know that in a planar Graph degree of a vertex not exceeds from 5.

In a planar graph degree of vertex can be more than 5. Example is a star graph.

Here they are asking for min degree.

 

---

@Satbir Sir,

Now i'm confused with this statement of Wikipedia and NPTEL lecture and then your statement that also looks true,

see the statement and interpret it->

 for finite planar graphs the average degree is strictly less than 6. Graphs with higher average degree cannot be planar.

                                                                     -Wikipedia.

Check it !

https://en.wikipedia.org/wiki/Planar_graph

---

@Aks9639

Planar graph with the center vertex of degree 6, but the min degree is 3

---

@Satbir sir

i correct myself I misinterpret the above statement 

the correct statement is following:

"Every planar graph contains at least one vertex with degree at most 5."

   

 

---

Dear Sir

Thanks for this ans. I just wanted to know why are we assuming minimum degree of all the vertices to be same, can’t every vertex have diff min degrees.

---

Can someone please to me,  how other options are not satisfying the equation?

Answer 2

Let the min-degree of $G$ be $x$. Then $G$ has at least $\left[|v|\times \frac{x}{2}\right]$ edges.

$\left[|v|\times \frac{x}{2}\right]\leq \left[\left(3\times |v|\right) -6\right]$

for $x=6$, we get $0 \leq {-6}$, Therefore, min degree of $G$ cannot be $6$.

Correct answer is (D).

---

$\text{An alternative approach,}$

Let the min_degree of a graph be $\text{'x'}$ , then

 $x\leq \left(\frac{2e}{n}\right)$,
given  , $e\leq \left(3n - 6\right)$          $\text{\{it will be planner graph\}}$
put the value of $e$ ,then min_degree will be ,

 $x\leq \frac{(2(3n-6))}{n}$
 $x\leq \frac{\left(6n - 12\right)}{n}$
 $x\leq \left( \frac{6n}{n} - \frac{12}{n} \right)$
 $x\leq \left(6 - \frac{12}{n}\right)$ ,
 when number of vertices is more , then value of

$\left(\frac{12}{n}\right)$ will be less , $\left(\frac{12}{n} = 0.000001 \text{assume}\right)$ ,

then min_degree will be ,

$x\leq \left(6 - 0.000001\right)$
$x\leq 5.999999$  , max value
$x\leq \text{floor value}\left(5.9999999\ldots \right)$
$x = 5$ , maximum value of min_degree of defined graph (i.e. planner graph)

Comments

ans is D or C??

---

If we put x=4 then

|v|*4/2<=3|v|-6

-1<= -6 becomes false

Plz explain.

---

@ diksha,

if you put x=4 then equation becomes -|V| <= -6 not -1 <= -6.

Answer 3

Given that, |E| ≤3 |V| − 6

We know that the inequality, min-degree ≤ 2|E| / |V| .

Put the value of |E| into inequality.

min-degree ≤ 6 - 12 / |V|

let min-degree is m.

m ≤ 6 - 12 / |V|

So our eqn will become , |V| ≥ 12 / (6-m) .

Apply hit and try to check all the options.

Option (a) 3   ,put m=3 then  |V| ≥ 4 .Yes, it is possible.

Option (b) 4 ,put m=4 then  |V| ≥ 6 .Yes ,it is possible.

Option (c) 5  ,put m=5 then  |V| ≥ 12 .Yes, it is possible.

Option (d) 6   ,put m=6 then  |V| ≥ 12/0 . It is NOT possible due to Divide by Zero or indeterminant state.

Therefore, min-degree of G cannot be 6.

The correct answer is (D) 6

Comments

No need to use hit and trial.

m ≤ 6 - 12 / |V|   , Now since |V| is a positive number, 12/|V| will be positive as well hence,  6- 12/|V| will be less than 6 [since we are deducting some positive number from 6 so, result will be definitely less than 6]

So, m ≤ (something less than 6)  implies----> m<6  

Answer 4

Summation of degree = 2* no. of edges

                                   = 2( 3V -6)

Let min degree be d, then

d*V<= 2*(3V-6)

d*V<=6V-12

Taking V on left side-

(d-6)*V<= -12

Multiplying both side by (-1)

(6-d)*V>= 12

Minimum value of d should be 6 to make left side positive as no. of Vertices can't be negative.

Thus minimum degree, d=6.

Comments

If d is less than 6 then also left side is a positive no ??