Backedges in a graph


#1

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 ?
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true and Statement 2 is false
c) Statement 1 is false and Statement 2 is true
d) Statement 1 is false and Statement 2 is false

Give me some explanation about backedge


#2

Answer C
Untitled


#3

Statement 1 is false and Statement II is true.

Statement I is correctly explained by @Anmol_Binani.
Additionally, as here nothing is mentioned so we are taking into consideration all types of directed graphs. i.e. Simple, Multi and Pseudo directed graphs.
But if it is specified explicitly that it is a simple directed graph then in that case statement I would be false.

Statement II is a direct logical implementation. You can check by drawing fewer graphs.

Reference: