Proof for BFS and DFS equivalence I'm trying to prove (by induction) that BFS in equivalent to DFS, in the sense that they return the same set of visited nodes, but I'm stuck in the middle of some of the cases.

Let $G$ be a directed graph and $u \in V(G)$. 

We want to prove that $  BFS(G,u) = DFS(G,u)$.



$\text{BASE CASE}$ 

$V(G) = \{u\}$

$BFS(G, u) = \{u\} \quad DFS(G,u) = \{u\}$

$BFS(G,u) = DFS(G,u) \quad Qed.$



$\text{INDUCTIVE HYPOTHESIS}$

$BFS(G,u) = DFS(G,u) \;\;\forall G, u \in V(G)$.



$\text{INDUCTIVE STEP}$

$(i)\;G' = (V(G) \cup\{v\}, E(G))$ 

We know that $BFS(G',u) = BFS(G,u)$ if $u \ne v$ (and so does $DFS$), because $v$ is disjoint from the rest of the graph, and so the proof follows from the hypothesis.

But if $u = v$ ?

$(ii)\;G' = (V(G), E(G) \cup (v,w)) \quad v,w \in V(G)$

How can I use the hypothesis here?
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$.