from 13minutes onwards

The Gateway to Computer Science Excellence

0 votes

+2 votes

Best answer

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

let component_{1} have n_{1} vertices, and component_{2} have n_{2} vertices, and ...component_{k} have n_{k} vertices

∴ n_{1}+n_{2}+...n_{k} = n

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

if component_{1} have n_{1} vertices ( and note that each component is connected. ) then minimum edges possible = n_{1}-1

if component_{2} have n_{2} vertices then minimum edges possible = n_{2}-1

.

.

.

if component_{k} have n_{k} vertices then minimum edges possible = n_{k}-1

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

52,218 questions

59,891 answers

201,086 comments

118,128 users