What is the effect of adding one edge on the number of spanning trees of a given graph ? Hi,
Define $C(G)$ the number of spanning trees in a graph $G$.
Now, given a graph $G$ with $n$ vertices and $p$ edges, construct a new graph $G'$ which is equal to the graph $G$ but where you add exactly one new edge.
The question is : can we know something about the fraction $\frac{C(G)}{C(G')}$ ? 
Perhaps we can use that the number of spanning trees of a graph is equal to the determinant of any cofactor of the laplacian matrix of the graph. (Because the two laplacian matrix are here very close) ? I tried in that way but without success yet.
 A: If the new edge connects vertices $v$ and $w$, then $C(G')/C(G) - 1$ is the electrical resistance between $v$ and $w$ in $G$ where all edges have a resistance of $1$. (Weighted versions work, too.) An upper bound for this resistance (providing a lower bound on $C(G)/C(G')$) is the distance between $v$ and $w$, and the maximum finite resistance occurs when $G$ is a path of $n$ vertices from $v$ to $w$, so that $C(G')$ is $n$ (spanning trees of a cycle) while $C(G) = 1$.
I would guess that the minimum resistance with $p=n+k$ edges occurs when the edge between $v$ and $w$ is as redundant as possible, with $k+2$ edges between them, with any forrest hanging off this repeated edge. That gives a resistance of $1/(k+2)$, and then $C(G) = k+2$ while $G(G') = k+3$. I think the minimum resistance is only slightly more complicated if you require the graphs to be simple: Maximize the paths of length $2$.
A: Sometimes, when dealing with concrete graphs, this bound can be handy. 
Let $f(G) = max_{u \not \sim v} C(G/uv)$ where $G/uv$ is obtained after contracting two non adjacent vertices $u,v$ of $G$ into a single vertex.
From the deletion contraction recurrence we know that $$C(G') = C(G+e) = C(G)+C( (G+e)/e) \leq C(G)+f(G)$$ from where you can easily get a bound for $\frac{C(G)}{C(G')}$
In the same manner you can obtain a lower bound for $\frac{C(G)}{C(G')}.$
