Let G be a simple undirected graph, TD be a DFS tree on G, and TB be the BFS tree on G. Consider the following statemets. - NET ASPIRANT ACADEMY

Answer: Option 3

Explanation: There are four types of edges can yield in DFS. These are tree, forward, back, and cross edges. In undirected connected graph, forward and back egdes are the same thing. A cross edge in a graph is an edge that goes from a vertex v to another vertex u such that u is neither an ancestor nor descendant of v. Therefore, cross edge is not possible in undirected graph.
So, statement (I) is correct.

For statement (II) take counterexample of complete graph of three vertices, i.e., K3 with XYZ, where X is source and Y and Z are in same level. Also,there is an edge between vertices Y and Z, i.e., |i-j| = 0 ≠ 1 in BFS. So, statement became false.

Download UGC NET Previous Question Paper.

Download Computer Science Syllabus

Mock Test on Computer Science

For more Details NTA NET ASPIRANT ACADEMY and YouTube Channel