search
Log In
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
1 vote
264 views

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

in Graph Theory
edited by
264 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..


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

Related questions

...