Number of spanning forests in a graph

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

Please refer to the following articles

C. J. Liu and Y. 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.

Y. Chow. On enumeration of spanning subgraphs with a preassigned cyclomatic number in a graph. Acta Mathematica Hungarica, 60(1):81–91, 1992.

C. J. Liu and Yutze Chow. Enumeration of forests in a graph. Proceeding of American Mathematical Society, 83(3):659–662, 1981.

Answer 4

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: Fermionic field theory for trees and forests which appeared in PRL. Follow ups such as Grassmann Integral Representation for Spanning Hyperforests can be found by looking at Sokal's papers on arxiv.

Note that there was a whole semester at the Isaac Newton Institute revolving around this topic: Combinatorial identities and their applications in statistical mechanics. 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.

Answer 5

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.