The Gateway to Computer Science Excellence
0 votes

Consider a simple connected undirected graph G which has m vertices and n edges. Which of the following condition always guarantee that after removal of those number of edges graph will be disconnected?

  • mn + 2
  • n – 2
  • None of the above
in Mathematical Logic by | 178 views

option B is mC2 -n+2

answer is n-m+2

1 Answer

+3 votes
Best answer

The key point here is :

We know a tree is a minimally connected graph..So if one less the number of edges in a tree is there , then it is always guaranteed that the resultant graph will be disconnected..

So given m vertices , n edges..

Hence no of edges in tree   =  m - 1

Hence one less will guarantee that the graph will be disconnected i.e. = m - 2..

Now initially we have n edges..Let no of edges to be removed  =  x..Hence 

          n - x =  m - 2

==>    x   =  n - m + 2

Hence D) is correct answer..

selected by
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
52,345 questions
60,513 answers
95,357 users