STCONN in $O(n)$ time?
Per the section quoted in the comments, it appears that one of the cited documents takes input in the form of an adjacency matrix. In this scenario, taking $s$ and $t$ to correspond to the first and last indices respectively, we can prove that $\Omega(n^2)$ bits of the matrix may need to be read to decide STCONN even under the promise that the $(n/2)\times(n/2)$ square blocks in the top-left and bottom-right are all ones (with the necessary adjustments for odd $n$).
Indeed, we have some $\Omega(n^2)$ entries unaccounted for in the matrix, and there is an $s$-$t$ path iff any one of them is a $1$. So in the worst case, we might need to read all of these $\Omega(n^2)$ bits to prove $s$-$t$-non-connectivity (or half of them if the graph is known to be undirected, which doesn't change the order of growth). We can turn this into a lower bound against randomized algorithms by considering the case that with 50% probability we either add or don't add in a $1$ uniformly at random: we must read some $\Omega(\varepsilon n^2)$ bits to gain a $\varepsilon$ advantage over a random coin flip.
Graphically, this corresponds to the case where $s$ and $t$ each lie within disjoint cliques of size $n/2$, and we wish to determine if there is at least one edge joining these cliques. One can also do the same thing with any other pair of connected structures of order $\Omega(n)$ each.