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 digraph 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?