in Graph Theory recategorized by
313 views
1 vote
1 vote
Prove that every graph with n vertices and k components has atleast n-k edges.
in Graph Theory recategorized by
313 views

1 comment

https://youtu.be/CiFPWWZvVHQ

 

from 13minutes onwards

0
0

1 Answer

2 votes
2 votes
Best answer

let there are 'n' nodes and k connected components.

let component1 have n1 vertices, and component2 have n2 vertices, and ...componentk have nk vertices

∴ n1+n2+...nk = n

we know that, minimum no.of edges requires to a connected graph with n vertices = n-1

if component1 have n1 vertices ( and note that each component is connected. ) then minimum edges possible  = n1-1

if component2 have n2 vertices then minimum edges possible  = n2-1

.

.

.

if componentk have nk vertices then minimum edges possible  = nk-1

 

total edges in the graph ( minimum ) = $\sum_{i=1}^{k} Edges\: in\: Component_{i}$ = (n1-1) + (n2-1) + .... +(nk-1) = (n1+n2+...+nk) - (1+1+....+1) = n - k

selected by

1 comment

@shaikh sir, i edited the question now ,

Nice explained
0
0