Number of spanning trees in random graph Let $G$ be a graph in $G(n, p)$ (Erdős–Rényi model). What is the (expected) number of different spanning trees of $G$?

There are $n^{n-2}$ trees on $n$ labelled vertices.  The probability that all $n-1$ edges in a given tree are in the graph is $p^{n-1}$.  So the expected number of spanning
trees is $p^{n-1} n^{n-2}$.
