GRAPH THEORY

Question

A graph G=(V,E)satisfies |E|≤3|v|-6, the min degree of G is defined asmin⁡{degree(v) } v∈V. Therefore min degree of ‘G’ can be?

A. 11

B. 4

C. 6

D. 5

Comments

is this 5?

---

@ sunil sarode 

wht is the given answer

---

Is it 4?

---

4 is given answer please explain how you got it ?

Answer 1

using:

$\delta \leq \frac{2e}{v} \leq \Delta$

|E|≤3|v|-6

$\delta \leq \frac{2(3v-6)}{v}$

$\delta \leq 6 - \frac{12}{v}$

if v=2 ,$\delta \leq$ 0

if v=3, $\delta \leq$  2

if v=4, $\delta \leq$ 3

if v=6, $\delta \leq$4

if v=12 $\delta \leq$ 5

min degree of ‘G’ can be 4

Comments

yes..

min degree means minimum in graph...and here we have taken  δ as min degree...and we got the relation

if v=6, δ≤4

if v=12 δ≤ 5

then δ could be 4,5...means min degree in the graph might be 4 or 5  ??

---

Akash why not 5?

---

@hs

 it should be minimum out of all possible values, that's why 4 will be the best choice.

I might choose 0 if that will present in the option.