G T Let be a simple undirected graph, D be a DFS G T tree on , and B be the BFS tree on G. Consider the following statements. G

Statement I : No edge of is a cross with T respect to D (u, v) G u

Statement II : For every edge of , if is i v j T at depth and is at depth in B then |i − j| = 1 . In the light of the above statements, choose the correct answer from the options given below

1. ABoth Statement I and Statement II are true
2. BBoth Statement I and Statement II are false
3. CStatement I is correct but Statement II is false
4. DStatement I is incorrect but Statement II is true.

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. Statement I is correct but Statement II is false

Explanation

In an undirected graph, DFS produces only tree and back edges — no cross edges (I true). In a BFS tree an edge's endpoints differ in depth by at most 1, and they can be at the same depth, so |i − j| = 1 is not always true (II false).