  We consider lower bounds on the number of spanning trees of connected graphs
with degree bounded by $d$. The question is of interest because such bounds may
improve the analysis of the improvement produced by memorisation in the runtime
of exponential algorithms. The value of interest is the constant $\beta_d$ such
that all connected graphs with degree bounded by $d$ have at least
$\beta_d^\mu$ spanning trees where $\mu$ is the cyclomatic number or excess of
the graph, namely $m-n+1$. We conjecture that $\beta_d$ is achieved by the
complete graph $K_{d+1}$ but we have not proved this for any $d$ greater than
3. We give weaker lower bounds on $\beta_d$ for $d\le 11$.
