559 views
Assume undirected graph G is connected . G has 6 vertices and 10 edges. Find the minimum number of edges whose deletion from graph G is always guaranteee that it will become disconnected
| 559 views

We know :

A tree is a minimally connected acyclic graph which contains n vertices and (n-1) edges..

Hence if a graph of n vertices contain less than (n-1) edges , then it will always guarantee that the resulting graph is disconnected..

So given we have 6 vertices and 10 edges at present..So

Minimum number of edges required for connectivity  =  5 edges..

So if a graph contains 4 edges it will be disconnected.

Hence no of edges that need to be deleted   =    10  -  4    =   6

by Veteran (102k points)
selected by
0
@Habib Sir

Graph with 6 vertices and 10 edges can be made with degree sequence <4,4,3,3,3,3>

after removing 3 edges my graph become disconnected with 5 vertices on one set and a 6th vertex on another,

so minimum should be 3 edges?

+1

@learner_jai

Look at the "Always guarantee" term in the question.

For the example you take it might happen, you required 3 edges removal. But it is not true for all the graph.

0
@Hemant Parihar,
Thanks
These silly mistakes, I try to reduce it.
0

Superb explanation  Habibkhan

+1 vote