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 Junior (939 points) | 156 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..

by Veteran (102k points)
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
50,644 questions
56,531 answers
101,355 users