#algo

Question

If a directed graph G is cyclic but can be made acyclic by removing one edge,then a depth-first search in G

will encounter exactly one back edge??

Answer 1

Yes,
Theorem:-> A directed graph has a cycle iff DFS reveals a back edge.

Means if there is cycle then there is compulsory back edge in DFS of G and vice versa.

So here as per ur question by removing 1 edge it becomes acyclic so, then definitely we encounter a Back edge when we do DFS of G.

U may take any no. of examples and cross verify it.

Comments

but here question is about " will it encounter exactly 1 back edge?" so would it be only one?

Answer 2

I hope it is clear now.

Comments

@ papesh  @ Rajesh Pradhan  Look at this solution.

---

According to the given solution the DFS after removal of A->B would be  B->C->A and the back edge would be B->A, C->A no longer remains the back edge . So this contradicts the given solution. I don't understand what I am missing in it,Can someone please explain ?

---

https://gateoverflow.in/145735/dfs-back-edge

@ Amrata Ramchandani 

visit this link and look at the comments.. you will get your answer. Thanks