This homework solution gives a proof that $L = \{G \mid \text{G is strongly connected directed graph}\} \in N\mathcal{L}$. One suggested way to proof that $L \in N\mathcal{L}$ by proving that $\bar{L} = \{G \mid \text{G is not strongly connected} \} \in NL$ and then using the fact $NL = coNL$.
The tutorial uses the following algorithm for $\bar{L}$:
- Nondeterministically select two nodes $(a,b)$
- Run $PATH(a,b)$. If it rejects, then the graph is not strongly connected, so accept. Otherwise reject.
Since $PATH$ itself is a nondeterministic algorithm (or rather, we have to use a nondeterministic algorithm to still be $N\mathcal{L}$, it is not clear to me why this is correct. Why is it okay to invert the answer of $PATH$ in this case?
For example, assume our nondeterministic choices wrongly lead us to believe there is no path between $a$ and $b$, then this nondeterministic branch would accept (which means our whole TM $M$ would accept, because there is one accepting branch). But if there is also a branch of $PATH$, then our graph $G$ might actually be strongly connected and $M$ will return a wrong answer by accepting.