# Conditions for a node to be a leaf node on DFS tree

Question: Consider the DFS tree generated by a DFS on a connected graph. Write below the necessary and sufficient condition for a node v to be a leaf node on the DFS tree. The condition must be in term's of v's discovery time d[v] and finishing time f[v].

I honestly have no idea what the answer to this question from a past exam may be...

The proof is obvious once you follow the DFS, marking each node's discovery time and finishing time. A leaf is defined as a node that has no children. Let $v$ be a node.
• Suppose $v$ has children in the final DFS tree. That is, we will go forward to a child $u$ of $v$ right after we have discovered $v$. That is, $d[v]+1 = d[u]$. The finishing time of $v$ must come after that. So f[v] $\gt$ d[v] + 1.
• Suppose $v$ has no children in the final DFS tree. That is, we will go backtracking once we have discovered $v$. That is, we will finish $v$ right after we have discovered it. That is, f[v] = d[v] + 1.