The Gateway to Computer Science Excellence
+1 vote
208 views

I think the explanation is for edges for which graph is always connected. 

in Graph Theory by Active (2.2k points)
edited by | 208 views

1 Answer

+5 votes
Best answer

Let a  SIMPLE graph with n nodes .
max no of edges possible are nC2.

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-1Cedges.

Total edges are n-1C2..

by Veteran (60.9k points)
selected by
0
The maximum number of edges to be included in G so that graph is not connected

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

=4851
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,226 comments
104,909 users