Form the product graph $\Gamma \times \Gamma$ whose vertices are pairs $(u, u') \in \Gamma \times \Gamma$ and paths $(p, p') : (u, u') \to (v, v')$ are pairs of paths $p : u \to v$, $p' : u' \to v'$. Let $\Delta = \lbrace (u, u) \mid u \in V(\Gamma) \rbrace$ be the diagonal. The question is then whether $\Delta$ can be reached from a given vertex $(x,y)$ in $\Gamma \times \Gamma$. This does not seem to be that hard to solve as it is just a [reachability][1] problem (if you want it in classical form, attach every vertex in $\Delta$ to a special vertex $\infty$ and ask for a path from $(x,y)$ to $\infty$).


  [1]: http://en.wikipedia.org/wiki/Reachability