94 views
Prove that every graph with n vertices and k components has atleast n-k edges.

recategorized | 94 views
0

from 13minutes onwards

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

by Veteran
selected
0
@shaikh sir, i edited the question now ,

Nice explained