retagged by
257 views
0 votes
0 votes

Statement I : If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge
Statement II : A graph G has a cycle if DFS finds at least 1 Backedge
Which of the following option is correct ?

  1.  Statement 1 is true and Statement 2 is true
  2.  Statement 1 is true and Statement 2 is false
  3.  Statement 1 is false and Statement 2 is true
  4.  Statement 1 is false and Statement 2 is false

according to me 3 option is correct(Statement 1 is false and Statement 2 is true

but answer given is 1,

please tell me where i am making mistake.

retagged by

2 Answers

0 votes
0 votes

Answer for the above question is option number 3 statement two is trivial (True) for statement one I can think of 2 possible scenario where the above case stands false.

First one:If a directed graph can be made acyclic by removing an edge then it is not necessary that it can break only one cycle multiple cycle  having common edge can be made acyclic by removing that edge and dfs can still fetch us more than one back-edge.

Second one:We can remove the back edge itself to make cyclic graph as non cyclic then during dfs creation we can have no back-edges.

Source:https://courses.csail.mit.edu/6.006/oldquizzes/solutions/quiz2-s2011-sol.pdf

Related questions