Recognizing strongly connected digraphs in NL

Question

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}$:

1. Nondeterministically select two nodes $(a,b)$
2. 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.

Answer 1

Because nondeterministic space classes are closed under complementation by the Immerman–Szelepcsényi theorem. So, you can't literally just invert the answer from $\text{PATH}(a,b)$ but the fact that there is an $\mathrm{NL}$ algorithm for $\text{PATH}(a,b)$ implies that there is also an $\mathrm{NL}$ algorithm for $\text{NOT-PATH}(a,b)$, and you use that.