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

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

in Graph Theory
edited by

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
The maximum number of edges to be included in G so that graph is not connected



Related questions