Dark Mode

313 views

1 vote

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