# 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

-

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.

-

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$.

-
And adding $s$ edges yields $\kappa(H + e_1 + \dots e_s) \leq \binom{s+n-1}{n-1} \kappa(H)$ by a similar argument. Can one improve this bound by taking advantage of the fact that when $\kappa(H)$ is big the spanning trees obtained from different spanning trees of $\kappa(H)$ necessarily overlap? –  David Harris Sep 13 '11 at 13:48
If $H$ has edge connectivity $c$, then each spanning forest of $H$ with exactly two components, one containing $u$ and the other containing $v$, can be made into a spanning tree of $H$ by adding at least $c$ different edges. In the other direction, as before a spanning tree of $H$ can be made into a 2-forest thing in at most $n-1$ ways. So $\kappa'(H) \le (n-1)\kappa(H)/c$, which I think implies that $\kappa(H+e) \le (n+c-1)\kappa(H)/c$. –  Brendan McKay Sep 13 '11 at 14:36

This seems to be exactly the subject of:

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")

-

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.

-
Isn't $\kappa(H) / \kappa(H+e)$ the probability that a random spanning tree of $H+e$ does not contain $e$? In which case we get the weak lower bound $\kappa(H+e) \geq \frac{d \kappa (H)}{d-1}$? –  Tony Huynh Sep 13 '11 at 8:40
If $H$ is a chain on $n$ vertices, then $\kappa(H) = 1$. Adding a single edge completes the chain to a cycle on $n$ vertices, so $d = 2$ but $\kappa(H + e) = n$. –  David Harris Sep 13 '11 at 13:43