retagged by
10,558 views

3 Answers

Best answer
6 votes
6 votes

Ans is C by formula (n-1)(n-2)/2 =99x98/2=4851  (graph should be simple i.e having no parallel edges and self loops)

e.g 2 disconnected graph with 2 nodes have 0 edge    (2-1)(2-2)/2=0

       disconnected graph with 3 nodes have  at most 1 edge   (3-1)(3-2)/2=1 

      disconnected graph with 4 nodes have at most   3 edges between 3 nodes and 4th node as isolated vertex (4-1)(4-2)/2=3

      disconnected graph with 5 nodes have at most  6 edges (5-1)(5-2)/2=6

in gen with n nodes (n-1)(n-2)/2

selected by
4 votes
4 votes

Answer C

When maximum number of edges are added and still 100 node graph is disconnected means we made a 99 node complete graph and left one node disconnected.

No of edges in complete graph of x nodes = x(x-1) /2 = 99(99-1)/2 =4851

I hope the concept is clear now

4 votes
4 votes

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

 

The maximum number of edges to be included in G so that graph is not connected 

=$\frac{(n-1)(n-2)}{2}$=$\frac{(99)(98)}{2}$=4851

 

Hence,Option(C)4851.

Answer:

Related questions

3 votes
3 votes
1 answer
1
go_editor asked Jul 20, 2016
10,287 views
A simple graph G with n vertices is connected if the graph has(n-1)(n-2)/2 edgesmore than (n-1) (n-2)/2 edgesless than (n-1) (n-2)/2 edges$\Sigma_{i=1}^k C(n_i, 2)$ edges...
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}$