edited by
555 views
0 votes
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?

  1. $m-n+2$
  2. $n-m$
  3. $n-2$
  4. None of the above
edited by

1 Answer

Best answer
3 votes
3 votes

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

Related questions

1 votes
1 votes
1 answer
1
Hira Thakur asked Nov 21, 2015
840 views
what is the sufficient condition so that we say given graph is planar or not???
0 votes
0 votes
3 answers
2
2 votes
2 votes
2 answers
3
angel rajput asked Feb 14, 2015
1,440 views
I just wanted to confirm that if I have a disconnected graph ,then I can call it planar .so for a graph to be planar do I need to check whether it is connected or disconn...
3 votes
3 votes
1 answer
4
dhingrak asked Dec 1, 2014
8,155 views
In a simple undirected graph with n vertices what is maximum no of edges that you can have keeping the graph disconnected?A) nC2 -1B) nC2C) n-1C2D n-1C2 - 1Ans is C) .......