The Question
I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c} \mathsf{there\;are\;two\;different}\\ \mathsf{simple\;paths\;from}\;s\;\mathsf{to}\;t\;\mathsf{in}\;G \end{array}\right.\right\} $$
where $G$ is a directed graph.
it's easy to show using a reduction to $\mathsf{PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c} \mathsf{there\;is\;a}\\ \mathsf{path\;from}\;s\;\mathsf{to}\;t\;\mathsf{in}\;G \end{array}\right.\right\} $ that $\mathsf{2-SIMPLE-PATH}\in\boldsymbol{{\tt NL}}-\mathsf{Hard}$.
What I'm unable to prove it that $\mathsf{2-SIMPLE-PATH}\in\boldsymbol{{\tt NL}}$. Is there a way to prove/disprove this? (if it's incorrect maybe so this is P-hard or something)
Failed Attempt
I tried using the following algorithm that's using logarithmic space, but it's incorrect: We use a Non-deterministic TM to randomly choose two different simple paths from $s$ to $t$. We create the two paths on-the-fly at the same time by each time randomally selecting the next vertex we visit (we randomally choose one vertex for each path), and we also keep track of what is the first time the two paths diverge, and we don't allow the 2nd path we create to come back to that first divergence point.
Basically this algorithm checks if there are two different paths, where the 2nd path doesn't return to the point where the two paths first diverged. I though this is equivalent to having two different simple paths, but as you can see in the example in the next image, this is wrong, as there's only one simple path from $s$ to $t$, but the paths $\begin{array}{c} s,1,{\color{red}{2}},3,4,5,6,1,t\\ s,1,{\color{red}{2}},5,6,1,t \end{array}$ indeed fit the description of my algorithm.
