Number of spanning forests in a graph

Hello,

I have two questions that have been bugging me recently. The first is about the number of spanning forests in a graph and the second is about enumerating these with edge labels.

Q1: I am aware of Kirchhoff's Matrix-Tree theorem regarding the number of spanning trees in a graph. I was wondering if there is a generalization to this theorem that counts the number of spanning k-forests in a graph. What I am mostly interested in is this: is there a method of finding the number of k-forests in a graph by taking a determinant of some matrix?

Q2: Suppose you label each edge as $e_{i,j}$ meaning that you are taking the undirected edge from $v_i$ to $v_j$ in the graph. Then in the Laplacian matrix if you plug in the sum of $e_{i,j}$'s instead of $\deg(v_i)$ and $-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get the combinatorial Laplacian. Taking the determinant of a minor of this matrix gives the Kirchhoff polynomial which is an enumeration of the spanning trees of the graph, where each monomial contains the variables for all the edges in the given tree. My question is whether we can generalize this to spanning forests.

-

5 Answers

Two points:

(1) There is a result which is very similar to this. Let $G$ be a graph. Let $A$ be the matrix whose rows and columns are indexed by the vertices of $G$, where $A_{ij}$ is negative the number of edges from $i$ to $j$, for $i \neq j$, and where $A_{ii} = \lambda_i + \deg_i(G)$. Then the coefficient of $\lambda_{i_1} \cdots \lambda_{i_k}$ in $\det A$ is the number of spanning forests of $G$ with $k$ components, such that $i_1$, $i_2$, ... and $i_k$ are in separate components. Notice that the case $k=1$ is the matrix tree theorem: The coefficient of $\lambda_{i_1}$ is clearly the determinant of the adjacency matrix of $G$, with the $i_1$-st rows and column deleted. Basically any proof of the matrix-tree theorem should prove this as well.

If you set all the $\lambda_i$'s equal to each other, then the coefficient of $\lambda^k$ in $\det(A)$ will be the weighted number of $k$-spanning-forests, where the weight of a forest with components $T_1$, $T_2$, ..., $T_k$ is $\prod |T_i|$. (Because that is the number of ways to choose $k$ vertices, one in each component.) Perhaps this is good enough for your purposes.

(2) It is highly unlikely that there is a reasonable formula which gives you an exact count. More precisely, counting spanning forests is a #P-complete problem. See On the Computational Complexity of the Jones and Tutte Polynomials and note that counting spanning forests is equivalent to evaluating Tutte at $(1,2)$. This means that, assuming $P \neq NP$, there is no polynomial algorithm to count spanning forests. Now, "reasonable formula" is not a precisely defined notion, but I suspect that anything you would consider reasonable would give a polynomial time algorithm. In particular, note that computing an $n \times n$ determinant, all of whose entries have at most $n$ digits, is polynomial time.

-
(1) Ooh! That is very useful! Does this matrix have a name? Where can I read about it? I compared the results of using this matrix with some results from a brute force code that I have and they match 1 to 1. Thank you very much David! Also, I think that if I put the same lambda on two vertices, I will be able to get the number of spanning forests such that these two vertices are in the same tree. Is this true? –  Aleks Vlasev Jun 1 '11 at 5:37
(2) As for enumeration, I'm not sure that enumeration is the right word in this case. What I meant is that I need a polynomial where each monomial is a product of variables $e_{i,j}$, each associated to one of the edges in the spanning forest. I wonder if I just use the same idea used in constructing graph polynomials - replace the degree with a sum of edge variables of edges attached to the vertex, i.e. $A_{i,i} = \lamba_i + \sum e_{i,k}$, where $k$ runs over all indices except $i$. As for the -1 entries, what if we replace them with $-e_{i,j}$. Would this give us what we need? –  Aleks Vlasev Jun 1 '11 at 5:45

I started this, went to dinner, and came back to see that David Speyer anticipated me, but I'll put it in anyway. Here is a theorem, a story and a result somewhat along the lines you want.

Theorem: If $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components of sizes $n_1,n_2,\cdots,n_k$ then the number $T(\mathcal{F})$ of completions to a labelled tree is $n_1n_2\cdots n_kn^{k-2}.$

The proof is left to the interested reader but it is an easy induction on $k \ge 1$ and includes at the other extreme of $k=n$ the usual enumeration of labelled trees. (see below)

Story: I discovered this as an undergraduate. Of course I knew that there are like 100 proofs of the $n^{n-2}$ theorem but I thought the induction on the number of undetermined edges might be a slightly new twist. I had the occasion to show it to Frank Harary who said: "This is well written and deserves a place in the literature, I am editing a new journal, submit it." So I did. A few months later it came back with a letter from Haray: "I got the referees report, never submit this anywhere again!" and I didn't (until now!).

So for your Q2: Label an edge from $v_i$ to $v_j$ as $e_{i,j}$ (with $i \lt j$). Then in the Laplacian matrix if you plug in $n-1+\sum_j e_{i,j}$ instead of $\deg(v_i)$ and $-1-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get a modified combinatorial Laplacian. Taking the determinant of any minor of this matrix gives a modified Kirchhoff polynomial which is a weighted enumeration of the spanning forests of the graph, where each term is a monomial contains the variables for all the edges in a given forest $\mathcal{F}$ and the coefficient is $T(\mathcal{F}).$ So this polynomial spits out all the spanning forests including the empty one (times $n^{n-2}$) ,each of the spanning trees, and everything in between.

Looking over the comments i see that one could just add the identity to the original combinatorial Laplacian (i.e. set all the $\lambda_{ii}=1$) and get a sum over the spanning trees with positive weights.

the proof The case $k=1$ is obvious (alternately, start with $k=2$.) Suppose now that the result is true for forests made of $k-1$ trees and that $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components $T_1,T_2,\cdots,T_k$ of sizes $n_1,n_2,\cdots,n_k$. We will find $(k-1)T(\mathcal{F})$, the number of ways to add a distinguished edge (obtaining a forest with $k-1$ components) and then complete that to a tree. If the distinguished edge goes from $T_i$ to $T_j$ then, by assumption, there are $(n_i+n_j)n_1n_2\cdots\widehat{n_i}\cdots\widehat{n_j}\cdots n_kn^{k-3}$ such completions. Since there are $n_in_j$ such edges, the number mentioned is $$\sum_{1\le i<j \le k}(n_i+n_j)\left(n_1\cdots n_kn^{k-3}\right)=(k-1)\sum_{i=1}^kn_i\left( n_1\cdots n_kn^{k-3}\right)=(k-1)n\left( n_1\cdots n_kn^{k-3}\right)$$ Hence, $T(\mathcal{F})=n_1n_2\cdots n_kn^{k-2}.$

-
Thank you for your answer Aaron! That's a fascinating story. I just don't understand the part about the referees report. Did the referee not like the proof? As for the question at hand, I tried out what you wrote in combination with what David wrote. The matrix I used is the following $A_{i,j} = \lambda_i + \sum_{k=1,k\neq i}^n e_{i,k}$ when $i = j$ and $A_{i,j} = - 1 - e_{i,j} when$i \neq j$. – Aleks Vlasev Jun 1 '11 at 6:14 I meant$A_{i,j} =−1−e_{i,j}$when$i \neq j$. The problems I am working on involve only graphs that are connected, have no loops, no multiedges. When I take the determinant of this matrix along the lines of what David suggested and pick off a given coefficient, say$[\lambda_1 \lambda_2 \lambda_3]$, I expect to get monomials that correspond to spanning forests that keep vertices 1,2 and 3 in different components but it seems like I get more that what I wanted. – Aleks Vlasev Jun 1 '11 at 6:18 Luckily it seems that for small cases like$K_5$and$K_6$, those extra terms either have a negative sign or they are non-linear in the edge variables or they do not have the correct number of edge variables, so I can just get rid of them. What is left is precisely what I needed. I tried the same with$n + \sum_j e_{i,j}$and the situation is very similar. However, if I use my above definition for$A_{i,i}$and$A_{i,j}=−e_{i,j}$, the determinant gives me precisely what I needed! My questions are, is my approach correct? Why did you have$−1−e_{i,j}$instead of just$-e_{i,j}$? – Aleks Vlasev Jun 1 '11 at 6:44 @Aleks I assume the referee said "100 proofs is enough!, I don't want to see another proof." In my humble opinion it is a short simple complete self contained proof. – Aaron Meyerowitz Jun 1 '11 at 17:01 Dear Aaron, please include the easy inductive proof that you discovered. The statement itself (regarding the number of trees containing a fixed forest was probably known well before (I heard about it as an undergraduate) I would look at J W Moon's book.For example, it can be proved using the formula of labelled trees with prescribed degree sequences (which itself is easily proved by induction.) There is a beautiful proof by Pitman regarding Cayley's formula that uses counting labelled rooted forests. – Gil Kalai Jul 15 '11 at 11:46 With regards to your Q2, in quantum field theory there is a commonly used generalization of the Kirchhoff polynomial to 2-trees (2-component spanning forests). It's normally called the 2nd Symanzik polynomial, as the 1st Symanzik polynomial is basically identical to the Kirchhoff polynomial. I'm not sure if it can generalize to$k$-spanning forests. To calculate the 2nd Symanzik polynomial you need to associate a variable with each vertex. (In QFT this is the incoming momentum at that vertex.) There's a nice recent review article which discusses some of this Feynman graph polynomials (arXiv:1002.3458v3) I also made a Mathematica demonstration that lets you draw graphs and calculates the polynomials. Scalar Feynman Diagrams And Symanzik Polynomials. The classic reference is N. Nakanishi, Graph Theory and Feynman Integrals, Newark, NJ: Gordon and Breach, 1971. - Thanks Simon, the Feynman graph polynomials paper is the first one I consulted when I looked at the problem. Thank you for the help! That Mathematica demonstration looks great! – Aleks Vlasev Jun 1 '11 at 5:59 @Aleks Not a problem. I knew it probably wasn't what you were after, but I put in my 2c when I can. If you liked the Feynman graph paper, then I suggest you have a look at Nakanishi. In a sense, arXiv:1002.3458 is just a shortened version of Nakanishi updated to use dimensional regularization. – Simon Jun 2 '11 at 13:22 Please refer to the following articles C. J. Liu and Yutze Chow. Enumeration of Connected Spanning Subgraphs Of A Planar Graph. Acta Mathematica Hungarica, 41(3):27–36, 1983. C. J. LIU and YUTZE CHOW. On Operator And Formal Sum Methods For Graph Enumeration Problems. SIAM Journal of Control and Optimization, 5(3):384–406, 1984. C. J. Liu and Yutze Chow. Enumeration of Connected Spanning Subgraphs Of A Planar Graph. Acta Mathematica Hungarica, 60(1):81–91, 1992. C. J. Liu and Yutze Chow. Enumeration Of Forests In Graph. Proceeding of American Mathematical Society, 83(3):659–662, 1981. - I am surprised no one mentioned the work of Alan Sokal and coworkers on precisely this issue of weighted enumeration of spanning forests which is related to the$q\rightarrow 0\$ limit of the Potts model as well as the multivariate Tutte polynomial.

A determinant expression corresponds to a Fermionic (Grassmann/Berezin) integral with a quadratic `action' in the exponential. There is an analogue of the matrix-tree theorem for spanning forests with a Fermionic integral with quartic action see: http://arxiv.org/abs/cond-mat/0403271

which appeared in PRL. Follow ups such as http://arxiv.org/abs/0706.1509

can be found by looking at Sokal's papers on arxiv: http://arxiv.org/find/grp_math/1/au:+sokal/0/1/0/all/0/1

Note that there was a whole semester at the Isaac Newton Institute revolving around this topic: http://www.newton.ac.uk/programmes/CSM/

One can even watch the videos of the talks. The one perhaps most relevant to this question is the talk by Andrea Sportiello in the fourth workshop.

-