365 views

2 Answers

1 votes
1 votes
a graph with (n-1) vertices can have a maximum of [ (n-1)(n-2) ] /2  edges .Incase if we try to add one more edge,then we might have to include that one isolated vertex as well and so the graph will become connected.
0 votes
0 votes
For any graph $(n-k)\leq e\leq ((n-k)(n-k+1))/2$

here put k=1 ( k is no of components)

so, $(n-1)\leq e\leq ((n-1)(n-2))/2$

any edge greater than ((n-1)(n-2))/2 will surely make the graph connnected

Related questions

0 votes
0 votes
1 answer
1
mb14 asked May 28, 2018
394 views
In this graph it is said that $a,e,b,c,b$ is a path. But according to definition- in a path vertices and edges can't repeat so why this is a path. confused please clarify...
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
Pavan Kumar Munnam asked May 12, 2017
377 views
algorithm to find more than one path between any two vertices of a graph G=(V,E) , with a complexity of O(VE) ?