retagged by
10,288 views

1 Answer

Best answer
4 votes
4 votes

A simple graph with n vertices is connected if if has more than $\frac{(n-1)(n-2)}{2}$ edges. 

The n vertex graph with  the maximal number of edges that is still disconnected is a Kn−1

a complete graph Kn−1 with n−1 vertices has $\binom{n-1}{2}$edges, so $\frac{(n-1)(n-2)}{2}$ edges.

Adding any possible edge must connect the graph, so the minimum number of edges needed to guarantee connectivity for an n vertex graph is $\frac{(n-1)(n-2)}{2}$+1

 

Hence,Option(B)More than $\frac{(n-1)(n-2)}{2}$.

selected by
Answer:

Related questions

4 votes
4 votes
3 answers
1
go_editor asked Jul 20, 2016
10,560 views
Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is2451495048519900
2 votes
2 votes
2 answers
4
go_editor asked Jul 21, 2016
1,926 views
What type of logic circuit is represented by the figure shown below ?$\text{XOR}$$\text{XNOR}$$\text{XAND}$$\text{XNAND}$