2 Added to the question in light of a first response.

Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is uniformly chosen over all such sets.)

Associated to the random forest $F$ are marginals $\{p_e:e \in E\}$, where $p_e = \mathbb{P}(e \in E')$. Now let $E^*$ be a random subset of $E$, chosen by independently including each edge $e \in E$ with probability $p_e$.

Finally, let $N$ be the (random) smallest number of spanning trees of $G$ whose union contains $E^*$.

What is known about the distribution of $N$? How does $\sup_{G} \mathbb{E}(N)$, the largest expected value of $N$ over all $n$-vertex graphs, grow? Is it $O(\log n)$? is Is it $O(1)$?

Edit: is it $O(\sqrt{\log n})$? Fedor has a nice example showing that it is not $O(1)$. I expect this may be well-understoodbelieve optimizing Fedor's example yields a lower bound of order $(\log n/\log\log n)^{1/2}$.

Note: the question also makes sense if $E'$ is the edge set of a uniformly random spanning tree, but not by meand Fedor's example applies in either case.

1

# Covering a random graph with spanning trees.

Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is uniformly chosen over all such sets.)

Associated to the random forest $F$ are marginals $\{p_e:e \in E\}$, where $p_e = \mathbb{P}(e \in E')$. Now let $E^*$ be a random subset of $E$, chosen by independently including each edge $e \in E$ with probability $p_e$.

Finally, let $N$ be the (random) smallest number of spanning trees of $G$ whose union contains $E^*$.

What is known about the distribution of $N$? How does $\sup_{G} \mathbb{E}(N)$, the largest expected value of $N$ over all $n$-vertex graphs, grow? Is it $O(\log n)$? is it $O(1)$?

I expect this may be well-understood, but not by me.