Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I hope I can avoid being confusing, but here goes.

I have a graph $(V, E)$, connected, undirected and with no loops. I also have an assignment of integer-valued weight to each edge of the graph. Note that this is the set up of the minimum spanning tree problem whose solution is well-know.

My question is: given an integer $n$, how many spanning trees are there of weight $n$? Is there a solution to compute this number? In other words, a function $f_{(V,E)}: \mathbb{N} \rightarrow \mathbb{N}$ that gives the number of spanning trees of a given weight. Perhaps something like Kirchoff's matrix tree theorem which gives you the total number of spanning trees.


share|cite|improve this question
You can compute the value for small $n$, then feed it to In this case, finds many choices but one is what you want. – Ross Millikan Feb 22 '12 at 5:23
@Ross: How can it be a known sequence? It depends on the graph and the assigned weights. – Brian M. Scott Feb 22 '12 at 5:43
Maybe if you replace the $(i,j)$ element in the Kirchoff matrix with $x^w$ where $x$ is an indeterminate and $w$ is the weight of the edge joining $i$ and $j$ you'll get a polynomial where the coefficient of $x^n$ is the number of spanning trees of weight $n$? Or maybe not, but see's_theorem, the section on "Explicit enumeration of spanning trees" looks something like what I'm suggesting. – Gerry Myerson Feb 22 '12 at 5:51
@GerryMyerson - oh that does reasonable. Thanks! (Of course now I seek a proof of that statement - I will give it a try or hunt around for one!) – Elden Elmanto Feb 22 '12 at 14:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.