Zeal Workbook: Graph Theory - Graph Connectivity

Question

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

Comments

https://youtu.be/CiFPWWZvVHQ

 

from 13minutes onwards

Answer 1

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

let component₁ have n₁ vertices, and component₂ have n₂ vertices, and ...component_k have n_k vertices

∴ n₁+n₂+...n_k = n

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

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

if component₂ have n₂ vertices then minimum edges possible  = n₂-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) + (n₂-1) + .... +(n_k-1) = (n₁+n₂+...+n_k) - (1+1+....+1) = n - k

Comments

@shaikh sir, i edited the question now ,

Nice explained