Determine if a tree is a DFS Tree

Question

Question goes as:

We know that there may be many possible DFS trees for a graph depending upon the start vertex and the order in which we explore the neighbors of each vertex.
Given a connected graph G = (V, E), you are given a rooted tree T such that each edge of this tree is present in E. Design an efficient algorithm to determine if T is a DFS tree of G.

What is the meaning of "tree T is not a DFS Tree" (assuming it spans the entire graph)?

If I don't have any ordering of tree vertices in the adjacency list representation (which I presume the question inherently claims), I could traverse in any fashion and create the tree that is given in the question.

EDIT : I think I came to know about a "non - DFS tree T", it is simply the tree that spans but isn't possibly creatable in any possible DFS, since we have a restriction that ALL children must be visited first in a DFS tree before returning to parent. Still, can anyone help with the efficient Algo.

eg:

A -- B
      /  \
     C - D

this graph has a Tree T as:
A -- B
      /  \
     C   D

but this isnt a valid DFS tree !
DFS starting at vertex A.

Thanks in advance!

Answer 1

The fact that DFS does not determine uniquely the resulting labeling is due to the fact that there is no order in which the children of a node are visited. To my understanding, checking whether a tree T of a given graph G is a DFS tree can be done as follows.

Find a node wich has the minimum label in T; this will be current node v which at this point is the root at which a DFS search is started. Mark v as visited.

Recursively process the unvisited children of v in G. If these are not the same as in T, T is not a DFS tree of G. If they are the same, process them in ascending order of their DFS numbers in T, assigning DFS numbers as usual and marking visitied nodes. Whenever the assigned DFS number does not match the DFS number in T, the tree T cannot be a DFS tree of G. If, on the other hand, all DFS numbers can be assigned to match those in T, we have constructively proven that T is a DFS tree of G.