is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?
I just realized, a single call to DFS is not sufficient, since the conjecture I asked about is not true. Here is a counterexample. Suppose DFS first visits all nodes in a tree rooted at $u$, and $v$ is a descendant of $u$. Then suppose an unvisited vertex $w$ has both $u$ and $v$ in its adjacency list. Then, $w$ would not be in the same tree as $u$ and $v$, but there would be cross-tree edges $(w, u)$ and $(w, v)$, and hence there would be more than two paths from $w$ to $v$, making the graph not singly connected.
However, we cannot modify the algorithm to also look for cross edges between trees, since if we removed the $(w,u)$ edge from the example above, then it's still possibly for it to be singly connected even though there's a $(w,v)$ cross edge.