The Gateway to Computer Science Excellence
+2 votes
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
in Graph Theory by Boss (10.2k points) | 559 views

1 Answer

+9 votes
Best answer

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
@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?

please guide


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.

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

Superb explanation  Habibkhan

Related questions

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,405 answers
105,465 users