Proof for BFS and DFS equivalence
There is not much hope in proving $BFS(G,u) = DFS(G,u)$ directly by mathematical induction on the number of nodes in $G$ or on the degree of $u$. The problem is that as an induction hypothesis that equality does not capture the &quot;right&quot; kind of information or cover the &quot;right&quot; cases that are useful for the induction step.
Approach one: the explicit description as reachable nodes
Instead, you can try proving separately that each side is equal to the set $R$ of reachable nodes from $u$, that is, $R=\{v\in V(G)\mid \mbox{ there is a directed path from } u \mbox{ to } v \}$. More specifically,
$$R=\{u\}\cup\left\{v\in V(G)\mid \mbox{ there exist } u_0, u_1, \cdots,u_n \text{ such that }u_0=u, u_n=v, u_i\in V(G) \text{ for } 0\le i\le n \text { and }(u_i,u_{i+1})\in E(G)\text{ for } 0\le i\lt n\right\}$$
You can prove the case of $DFS$ by mathematical induction on the total number of nodes of $G$. You can prove the case of $BFS$ by mathematical induction on the distance of $v$ to $u$. Or use whatever as you see fit.
Approach two: the characterization as nodes closed under neighbourhood
A set of nodes $S$ is said to be closed under neighbourhood if for any node $n$, $S$ contains the adjacent nodes of $n$. That is, if $n\in G$ and $(n, m)\in E(G)$, then $m\in S$. Here are the critical observations on both $BFS$ and $DFS$.
Lemma 1. $DFS(G,u)$ is closed under neighbourhood.
Proof: It becomes obvious once we check what $DFS$ does when it discovers a new node.
Lemma 2. $BFS(G,u)$ is closed under neighbourhood.
Proof: It becomes obvious once we check what $BFS$ does when it pops out a node from the queue.
Lemma 1 and 2 suggest us to consider the minimal set of nodes that contains $u$ and closed under neighbourhood. Name it $C(G,u)$. It is enough to prove that both $BFS(G,u)$ and $DFS(G,u)$ are equal to $C(G,u)$. We have shown both contain $C(G,u)$. It is easy to verify &quot;the set of nodes visited so far are contained in $C(G,u)$&quot; is an invariant of $BFS$ on $G$ starting from $u$. The same hold for $DFS$.