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

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.