854 views
0 votes
0 votes
Consider an undirected graph G with 100 nodes. What is the maximum number of edges to be included in G so that graph is connected?

(a) 2451

(b) 4851

(c) 4950

(d) 9990

2 Answers

3 votes
3 votes
Maximum number of edges to make graph connected is $\frac{n*(n-1)}{2}$

$\frac{100*99}{2}= 4950$

so C
0 votes
0 votes

Two ways of interpreting this question : 

1) For maximum, it will be same as maximum edges that can be present in a simple graph (Assuming it is not a Multi-graph). that is n(n-1)/2 = 4950. Coz a complete graph is always connected and will have maximum possible edges. 

2) But if the question is, what is the maximum number of edges that are possible so that if you add one more edge then it will be connected otherwise not. So we can imagine an isolated vertex and Kn-1 graph. Now if you add just an edge to the isolated vertex, then it will be connected and number of edges in that case would be $\frac{(n-1)(n-2)}{2}+1$ = 99*98/2 + 1 = 4852 (Which is not given in option).

So I guess first interpretation is correct and answer is 4950. 

Related questions

1 votes
1 votes
1 answer
3
admin asked Apr 2, 2020
506 views
Degree of each vertex in $K_n$ is $n$$n-1$$n-2$$2n-1$
0 votes
0 votes
2 answers
4
admin asked Mar 31, 2020
2,020 views
The number of ways to cut a six sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is$13$$14$$12$$11$