  In this note, we show that three graph properties - strong connectivity,
acyclicity, and reachability from a vertex $s$ to all vertices - each require a
working memory of $\Omega (\epsilon m)$ on a graph with $m$ edges to be
determined correctly with probability greater than $(1+\epsilon)/2$.
