title: Determine if a tree is a DFS Tree
body: <p>Question goes as:</p>
  
  <blockquote>
    <p>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.<br>
    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.</p>
  </blockquote>
  
  <p>What is the meaning of "tree T is not a DFS Tree" (assuming it spans the entire graph)?</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>eg: </p>
  
  <p>A -- B<br>
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/&nbsp; \<br>
     &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C - D</p>
  
  <p>this graph has a Tree T as:<br>
  A -- B<br>
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/&nbsp; \<br>
     &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C &nbsp; D</p>
  
  <p>but this isnt a valid DFS tree !<br>
  DFS starting at vertex A.</p>
  
  <p>Thanks in advance!</p>