Graph Theory | find a simple path by DFS Hi. would love a bit of help with a question I'm stuck on from a course I'm taking. Anything helps.
Let be $G=(V,E)$ an arbitrary digraph and let be $w,v,u$ arbitrary vertices. Prove that there is a simple path from $u$ to $v$ that goes through $w$ iff there is a DFS scan from $u$ that satisfies $$u.d<w.d<v.d<v.f<w.f<u.f.$$
Here, for a vertex $x$, $x.d$ denotes the "time" vertex $x$ was discovered, and $x.f$ denotes the "time" we finished checking every edge that comes out of $x$.
My approach: It seems logical to me that if we started with $u$, then found $w$, found $v$ and finished analyzing every vertex in the opposite order, the claim is true, for both sides, because it definitely claims that we find $w$ through $u$ and $v$ through $w$, because by definition there is a simple path from $u$ to $v$ if $u.d<v.d<u.f<v.f$, but I feel that's a bit too easy of a solution for it to be true.
Thanks in advance for every comment!
 A: It looks like you have some intuition for why the statement is true, but have trouble backing it up with very specific reasons.
You say

By definition there is a simple path from $u$ to $v$ if $u_d < v_d < u_f < v_f$.

(I'm going to use subscripts rather than $.$'s because I think it looks prettier.)
This is true; it's not true by definition. The definition of a simple path doesn't have anything to say about DFS scans, and the definition of a depth-first search only talks about neighbors of vertices, not paths.
Anyway, the key pair of vertices to think about is $w$ and $v$, not $u$ and $v$ or $u$ and $w$. (It's true that there are simple paths from $u$ to $v$ and $w$ because $v_d$ and $w_d$ both exist: $v$ and $w$ can be discovered by a DFS scan from $u$, so there are paths to $v$ and $w$ from $u$.)
Because $w_d < v_d < w_f$, we know that the vertex $v$ was discovered


*

*after we discovered $w$ from $u$, but

*before we finished exploring the vertices that can be reached from $w$.


This tells us that $v$ is one of the vertices that can be reached from $w$, and so there is a path from $w$ to $v$. This is the argument that you probably have in mind when you say that "by definition" there is a simple path.
So now we know that there is a simple path from $u$ to $w$ and a simple path from $w$ to $v$. This does not, however, imply that there is a simple path from $u$ to $v$ that goes through $w$. To get this, we have to argue that the path from $w$ to $v$ uses entirely separate vertices from the path that goes $u$ to $w$.
This, in turn, is true because the part of the DFS scan between time $w_d$ and $w_f$ never looks at the vertices that we took to get from $u$ to $w$. Those vertices were discovered before time $w_d$: the DFS scan at this point might see edges to those vertices, but it won't take them, because they've already been discovered.
Finally, you should argue that if there is a simple path from $u$ to $w$ to $v$, then there is a DFS scan that discovers all those vertices in the order we want. Well, there's a DFS scan that takes this simple path as the very first sequence of edges it looks at. You can check that for this DFS scan, no matter what it does next, we'll have $$u_d < w_d < v_d < v_f < w_f < u_f.$$
