Ace material

Question

If a graph with 10 vertices having each vertex having degree >=5 find graph connected or disconnected

Comments

if every vertex degree ≤ 5, then there may be some graph is disconnected

if every vertex degree > 5, then there is no simple graph exist which is disconnected.

But given that,

if every vertex degree ≥ 5, then there is a simple graph exist which is disconnected.

consider the case, every vertex has degree 5 ==> total edges = (10*5)/2 = 25

K_5,5 is have 25 edges with 10 vertices , which have 2 connected components ===> Disconnect

Answer 1

it should be disconnected.

I will take worst case case to prove it .

As Each vertex has degree $>=5$,let's assume it the minimum i.e $5$

By handshaking lemma,

$\sum \text{degree of vertices}=2 \times |\text{edges}|$

$5 \times 10= 2\times |\text{edges}|$

$|\text{edges}|=e$

$e=25$

But to be connected, minimum number of edges should be

$e>=\binom{n-1}{2}+1, \text{n=number of vertices}$

But $e=\binom{9}{2}+1=37 \nleqslant 25$

Hence disconnected

Comments

 

e>=C(n−1, 2)+1, n=number of vertices

it is sufficient condition but not necessary

necessary condition is e ≥ n-1

moreover in your case, degree of the node  ≥ 5 is false for the special node

---

It's connected every vertex having min degree of 5 it means every vertex  connected to atleast 5 vertices.so no vertex will be left isolated after joining these vertices with min degree of 5

---

Read my comment on the question