Spanning trees of $H \cup e$ in terms of $H$ 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
 A: 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.
A: Here is a proof that $\kappa(H+e) \leq n \kappa(H)$.  
Observe that $\kappa(H+e) = \kappa(H) + \kappa'(H)$, where $\kappa'(H)$ is the number of spanning forests of $H$ with exactly two components, with one containing $u$ and the other containing $v$.  For any spanning tree of $H$, there is a unique path from $u$ to $v$.  Deleting any edge along this path produces such a forest.  Since such a path contains at most $n-1$ edges, each spanning tree of $H$ generates at most $n-1$ such forests.  Therefore, $\kappa(H+e) \leq n \kappa(H)$ as claimed.
Note that this bound is tight for an infinite family of graphs.  Namely, let $H$ consist of a path from $u$ to $v$.  Then $\kappa(H)=1$, while $\kappa(H+uv)=n$.    
A: This seems to be exactly the subject of:
http://gradworks.umi.com/31/89/3189623.html
In particular, the "Feussman formula" cited in the abstract would seem to be useful (this is used to prove the matrix tree formula in Bollobas' "Graph Theory")
A: Here is a simple bound. If $H$ is connected and $e=(v,w)\notin E(H)$, let $d$ be the degree of $v$ in the graph $H+e$. Then $$\kappa(H+e)\le d\kappa(H).$$ Proof: $\kappa(H)/\kappa(H+e)$ is the probability that a (uniform) random spanning tree of $H+e$ contains $e$.  There is a well known way of generating a random spanning tree, which someone will give us a citation for: start at $v$ and walk at random, marking each edge which is the edge along which you first visit any vertex.  Stop when you have visited every vertex, then you have a random spanning tree. Therefore, $\kappa(H)/\kappa(H+e)$ is the probability that the random walk crosses $e$ from $v$ to $w$ before $w$ is visited any other way, which you can see is at least $1/d$ by considering the first step of the walk.
If I remember correctly, there are sharper bounds if $H+e$ is regular.
EDIT: Tony Huynh's comment below is correct and my lovely theorem is kaput!  Oops.
