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

=(n−1)(n−2)/2

=4851

=(n−1)(n−2)/2

=4851

5 votes

Best answer

Let a SIMPLE graph with n nodes .

max no of edges possible are ^{n}C2.

if we want to disconnect graph then do one thing just partition original graph in two portion with 1 and n-1 nodes respectively.

now find number of edges in each component.

with 1 node : no edge

with n-1 nodes : ^{n-1}C_{2 }edges.

Total edges are ^{n-1}C_{2..}