JNUEE-2016

Question

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

Comments

included or excluded

---

included

---

(d) is right

Answer 1

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

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

so C

Answer 2

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 K_n-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.