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.

  • 2
    $\begingroup$ Since all spanning trees of $G$ are spanning trees of $G^\prime$, you're asking what fraction of spanning trees of $G^\prime$ don't use the added edge. I doubt this will make proving anything easier but it might help the intuition. $\endgroup$ Jul 10 '12 at 16:51
  • $\begingroup$ What is the motivation for the question? $\endgroup$ Jul 10 '12 at 17:02
  • $\begingroup$ you might want to look at various versions of Weighted Matrix Tree Thm, see e.g. math.uwaterloo.ca/~dgwagner/Networks.pdf $\endgroup$ Jul 11 '12 at 7:36

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


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')}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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