Calculating total number of spanning trees containing a particular set of edges

Question

I have tried the following approach:

First I do edge contraction for all the edges in the given set of edges to form a modified graph.

Then I calculate the total number of spanning trees, using the matrix tree theorem, from the modified graph.

I want to know if this method is correct and if there are some other better methods.

Zena

It should be OK. As Adam Crume pointed out, you are now working with multigraphs. Fortunately there exists a version of the matrix tree theorem for multigraphs, which requires a slightly different laplacian matrix – Tribesman

Thanks. Are there any other approaches? I thought of this method just out of intuition. – Zena

Answer 1

Let G be a graph, let e be an edge, and let G/e be the same graph with e contracted. Then,

Proposition: There is a bijection between the spanning trees of G that contain e, and the spanning trees of G/e.

This proposition is not hard to prove; you're better off understanding the proof yourself instead of just asking other people whether it's true. Obviously if you have a spanning T tree of G that contains e, then T/e is a spanning tree of G/e. The thing to think through is that you can also go backwards.

And, as Adam points out, you have to be careful to properly handle graphs with parallel edges and graphs with edges from a vertex to itself.

Percolator

Answer 2

I don't know if it's correct or not, but you'll have to be careful of the fact that edge contraction can lead to parallel edges. You'll have to make sure that trees differing only by which parallel edge is used are counted as being distinct.

Hax