3
$\begingroup$

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

Improve this question
$\endgroup$

4 Answers 4

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – David Harris
    Sep 13, 2011 at 13:48
  • $\begingroup$ 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$. $\endgroup$
    – Brendan McKay
    Sep 13, 2011 at 14:36
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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}$? $\endgroup$
    – Tony Huynh
    Sep 13, 2011 at 8:40
  • $\begingroup$ 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$. $\endgroup$
    – David Harris
    Sep 13, 2011 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.