# Applications of the number of spanning trees in graphs

Let $G$ be a simple graph and denote by $\tau(G)$ the number of spanning trees of $G$.

There are many results related to $\tau(G)$ for certain types of graphs. For example one of the prettiest (to me) is that if $C_n^2$ denotes the square of a cycle, then

$$\tau(G) = n^2 f_n$$

where $f_n$ is the $n$'th Fibonacci number.

What I am wondering is if there are any known applications (practical and theoretical) of knowing $\tau(G)$ for certain graphs?

-
 Did you find out any?Even Im searching for one.. – user30645 May 4 '12 at 18:56 Yeah there are some applications! I'll write an answer soon – Jernej May 9 '12 at 10:07 This is related to resistances in circuits, but I don't remember the exact statement. – Qiaochu Yuan Jul 5 '12 at 15:42

Belief propagation on random fields, a technique used to calculate the marginals of a distribution in applications such as image processing, comes in handy when the graph represented by the random field is not complicated (with less cycles, average degrees, etc.). So far, we know that the solutions from belief propagation are exact if the underlying graph is a tree (not loopy).

I have seen some work that try to reduce complex graphs into their spanning trees to do exact inference while keeping the important properties of the original graph. So the number of spanning trees may tell something about the likelihood of a certain random field being able to be efficiently sparsified for approximate marginal solutions.

-

By the Matrix Tree Theorem $\tau(G)$ equals the cofactor of the graph Laplacian of $G$. Usually the Matrix Tree Theorem is applied to compute $\tau(G)$, but it might be also used in the other direction, namely, to compute the cofactor of the graph Laplacian.

Here is one example for this: The currently best algorithm for realizing planar 3-connected graphs as 3d polytopes with small integer coordinates, produces first an embedding with rational coordinates that will be scaled to integrality. The scaling factor can be deduced from the cofactor of the Laplacian of the graph of the polytope. In order to bound the grid size of the embedding one uses a bound on the maximal number of spanning trees in planar graphs.

See Small Grid Embeddings of 3-polytopes by Ribó, Rote, and Schulz.

-

As Qiaochu Yuan mentions in his comment, the number of spanning trees has relevance in electrical network theory, which again have implications for random walks in graphs. There is some material in Chapter 9 of http://www.student.dtu.dk/~s082951/01227/01227-GraphTheory.pdf

-