Suppose we have a connected graph $H$ with $m$ edges and $n$ vertices, and we add an edge to it. How can one bound the number of spanning trees of $H \cup e$ in terms of $H$? 


The following formula seems very plausible: if $\kappa(H) = \binom{m'}{n-1}$, then $\kappa(H \cup e) \leq \binom{m' + 1}{n-1}$. 


In particular, this formula is easily seen to be true if $m' = n-1$ (the minimal possible value) and $m' = m$ (the maximal possible value).


Is there a quick reference or proof for this bound or something like it?


Thanks for the help



Spanning trees of $H \cup e$ in terms of $H$
I get the following counterexample: Let $H$ be the graph on $12$ vertices, called $u\_1$, $u\_2$, ..., $u\_{6}$, $v\_1$, $v\_2$, ..., $v\_{6}$ with the following edges: $(u\_i, u\_j)$ and $(v\_i, v\_j)$ for all $1 \leq i < j \leq 6$, and $(u\_1, v\_1)$. Let the additional edge $e$ connect $(u\_2, v\_2)$.


The graph $H$ has $1,679,616$ spanning trees; $H \cup \{ e \}$ has $4,478,976$ spanning trees. We have
$$1679616 < \binom{24}{11} < \binom{25}{11} < 4478976.$$


To find this, I guessed that the counterexample would involve a graph that had two very dense components, connected by only a few edges, one of which was $e$. I then used Mathematica to experiment with the size of the two complete graphs at the ends until it found a counterexample. Replacing $6$ with higher numbers seems to give many more counterexamples.


