The Gateway to Computer Science Excellence
0 votes
Prove that every graph with n vertices and k components has atleast n-k edges.
in Graph Theory by Loyal
recategorized by | 94 views


from 13minutes onwards

1 Answer

+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

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

Nice explained
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,891 answers
118,128 users