We show optimal lower bounds for spanning forest computation in two different models:

* One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of n vertices. The sole allowed query asks for a spanning forest, which the data structure should successfully answer with some given (potentially small) constant probability 0"> 0 . We prove that any such data structure must use ( n log 3 n ) bits of memory.

* There is a referee and n vertices in a network sharing public randomness, and each vertex knows only its neighborhood; the referee receives no input. The vertices each send a message to the referee who then computes a spanning forest of the graph with constant probability 0"> 0 . We prove the average message length must be ( log 3 n ) bits.

Both our lower bounds are optimal, with matching upper bounds provided by the AGM sketch \cite{AhnGM12} (which even succeeds with probability 1 − 1 pol y ( n ) ). Furthermore, for the first setting we show optimal lower bounds even for low failure probability , as long as 2^{-n^{1-\epsilon}}"> 2 − n 1 − .