# The Inverse Spanning Tree Problem

* What graphs have a given number of spanning trees *

Gustav Kirchhoff is famous for his work on electrical circuits: his rules, called Kirchhoff’s laws, are widely used in electrical engineering. He also proved a theorem that allows the number of spanning trees to be computed, for any graph in polynomial time.

Today, I plan to talk about his famous spanning tree formula, which is often called the *Matrix Tree Theorem*. It arises in many places, and recently one of my graduate students, Farbod Shokrieh, has found a new interesting application. I was traveling the last few days and was in a meeting all day–each day–and so this one will be shorter than usual.

** Matrix Formula for Spanning Trees **

The matrix tree formula is a truly remarkable theorem. We are so used to counting being hard, that it may come as a shock–if you have not seen it before–that there is an exact formula for the number of spanning trees. Moreover, the formula, since it is expressed as a determinant, can be computed exactly in polynomial time. Too bad Kirchhoff did not create a determinant formula for the number of colorings of a graph.

Let be any graph, and let be its adjacency matrix and its degree matrix: the latter is the diagonal matrix with the vertex degrees on the diagonal. The *Laplacian* matrix of is equal to . The Kirchhoff theorem is stated as follows.

Theorem:The number of spanning trees of is equal to the absolute value of any cofactor of .

Recall, for any square matrix , a cofactor is the determinant of the matrix that is obtained by deleting a row and column from .

** The Inverse Spanning Tree Function **

The usual question that is studied, concerning spanning trees, is given a graph, how many spanning trees does the graph have? That is of course answered by the matrix theorem. However, we often want to know more information. A typical question might be: for this family of graphs what is the exact number of spanning trees as a nice formula; or if that is too hard, what is the approximate number of spanning trees?

Farbod’s research, which is joint with Matt Baker, concerns the structure of the *Jacobian* of a graph. The Jacobian is an abelian group that is associated with every undirected graph: the size of the Jacobian is equal to the number of spanning trees of the graph. I plan a more detailed post on this pretty research in the near future.

For now let’s just say that Farbod desires an answer to the following *inverse problem*: let denote the number of vertices of the smallest graph that has exactly spanning trees. Of course, must be a non-zero natural number. We avoid which arises from any disconnected graph. Thus, we put the “cart before the horse”–we give the number of spanning trees and ask for the graph. We want an inverse Kirchhoff matrix theorem, a theorem that tells us how to create a graph with a given number of spanning trees. This may be well known, but we do not know the answer–if you have it, we would be thrilled to hear from you.

** Basic Properties of **

The first question is whether or not is always well defined. More simply, given any , is there at least one graph with that number of spanning trees? The answer is yes,

Theorem:For any positive natural number ,

Consider a cycle of vertices. There are exactly spanning trees, deleting each edge yields a distinct spanning tree. *(Per comments, this needs to keep graph simple.)*

In general, what is the behavior of the function? A simple property of this function is,

Theorem:For any , the value of is at most

The proof of this is quite simple. Let be a graph with spanning trees, and let be a graph with spanning trees. Select a vertex in , and a vertex in . Then, create a new graph that consists of and with one new edge joining and . Clearly, all spanning trees of must use the new edge. However, any spanning tree of and form a unique spanning tree of .

** Primes **

A fundamental problem, is how does the function grow? What numbers , make small, and which numbers make the function large? These are the types of questions that Farbod needs to understand. A concrete example, is suppose that is a prime, can be small for prime ? By small he would like that

where is a constant. Or failing that he would like that there are an infinite family of primes and another number polynomial in the size of , so that

We cannot resolve these questions, but can relate them to many other open number theory questions. There are some graphs, for which the number of spanning trees is known in a more convenient form. For example, for a *fan* on vertices, the number of spanning trees is where is the Fibonacci number–see this pretty paper. A fan on vertices consists of a line of vertices, and one special vertex that connects to each vertex of the line: it looks a bit like a “fan.” (The figure is from the same paper.)

Theorem:Let be the fan on vertices, where is prime. Then, has spanning trees where is at most polynomial in .

The proof of the theorem depends on a simple fact about Fibonacci numbers.

From the above fact, it follows that , for some . And, we already know that the fan has spanning trees. Also, note that is bounded as claimed.

This theorem shows that, . It is unknown currently whether or not is prime for an infinite number of , so the theorem may or may not be useful.

** Open Problems **

What can you say about the function ? Can it be small for prime? More generally, is always small? Note, a simple counting argument to try and prove a lower bound does not seem to work: the number of graphs on vertices is exponential in , so perhaps is *always* polynomial in the size of ?

Finally, can we compute in polynomial time?

Prof. Lipton,

Is the Jacobian the same thing as the “critical group” of a graph (from chip-firing games)?

This group has appeared in the literature under many different names; in theoretical physics it was first introduced as the “abelian sandpile group” or “abelian avalanche group” in the context of self-organized critical phenomena. In arithmetic geometry, this group appeared as the “group of components” in the study of degenerating algebraic curves. In algebraic graph theory this group appeared under the name “Jacobian group” or “Picard group” in the study of

flows and cuts in graphs. The study of a certain chip-firing game on graphs led to the definition of this group under the name “critical group”.

When defined as critical group or sandpile group, the group law is quite “artificial”. That’s why I prefer to think of it as the “Jacobian”…

Is there a reference you can point me to for the “Jacobian” definition of this graph? I know a (very) little bit about the critical group, but haven’t seen these other definitions.

Harrison: Here are the links:

The lattice of integral flows and the lattice of integral cuts on a finite graph, by Bacher, La Harpe, Nagnibeda

Algebraic Potential Theory on Graphs, by Biggs

Riemann-Roch and Abel-Jacobi theory on a finite graph, by: Baker, Norine

I believe I learned about the Jacobian under the name “critical group”; if it’s isomorphic to the group I’m thinking of, it can be defined in terms of a chip-firing game with a sink being played on the graph.

Anyway, this is a very interesting problem. You aren’t allowing multiple edges or loops, right?

I think multiple edges are required in order to construct a graph with precisely 2 spanning trees.

Yes. It is the same as the

chip firing game. I should have said that.Also for the inverse problem I believe that am mainly interested in simple graphs, i.e. no multiple edges or loops. Thus, I made an error when stated the theorem on all values are possible: the cycle would be degenerate if S was not more than 2.

Isn’t it true that if S=n^{n-2} (for some ineteger n), then k(S)=n, since the complete graph on n vetices has n^{n-2} spanning trees and any smaller graph has less than this many spanning trees? Doesn’t it mean that k(S)=logS/loglogS for infinitely many values of S?

Yes it does. But that says nothing about the value of k(S) for general S. Right? The interesting case is what is k(p) where p is a prime.

Here are the first 500 values except for S in {13,22,34,38,47,107,122,218,466,475}, which are all 10 or more. The values for 0 and 1 depend on the exact wording of definitions. Except for 475, all the values greater than 9 are primes or two times a prime.

These were produced by brute force. It might be possible to check graphs

with 10 or more nodes, but it would require more optimization.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

=========================================================================================

00 | 2 0 Inf 3 4 5 6 7 4 5 10 5 5 >9 6 6 4 7 8 7

20 | 5 5 >9 8 5 9 8 7 6 6 6 9 6 7 >9 6 6 7 >9 7

40 | 5 7 8 7 7 5 7 >9 6 7 7 7 6 8 6 6 6 8 8 8

60 | 6 6 9 7 6 8 6 8 7 6 8 9 7 7 9 5 7 9 9 7

80 | 7 6 7 9 7 7 9 7 7 7 7 7 8 7 7 7 6 8 7 6

100 | 6 7 8 8 6 7 8 >9 8 8 7 6 7 8 6 6 8 7 8 8

120 | 6 6 >9 9 7 5 8 8 6 8 6 8 7 8 8 6 7 8 8 7

140 | 7 7 8 9 7 8 9 8 7 8 9 7 7 7 7 7 7 9 9 7

160 | 7 8 7 7 9 7 7 9 7 7 9 7 7 9 9 7 7 7 7 8

180 | 6 7 9 7 7 6 8 7 8 7 7 7 6 9 7 7 7 9 8 7

200 | 6 8 9 8 7 7 9 7 8 6 8 8 8 8 8 8 6 9 >9 9

220 | 8 8 8 8 6 6 8 8 8 8 8 7 8 8 8 8 7 8 8 8

240 | 7 8 7 7 8 7 8 8 7 8 8 8 8 8 9 7 7 7 8 8

260 | 7 8 8 8 7 8 8 8 8 8 8 8 7 7 9 7 7 8 7 7

280 | 8 7 9 8 7 7 8 7 7 7 8 7 8 8 8 8 7 7 9 7

300 | 6 8 9 8 8 7 8 8 7 8 9 9 8 7 8 7 9 9 8 8

320 | 7 7 9 7 6 7 7 7 8 7 7 9 8 8 8 7 6 9 7 7

340 | 7 8 8 9 7 7 9 9 8 9 8 7 7 7 7 7 8 9 9 9

360 | 6 7 9 8 8 9 9 9 7 8 9 9 7 9 8 7 8 7 8 9

380 | 8 9 9 8 6 7 7 9 8 8 8 8 7 8 8 8 8 9 8 7

400 | 7 8 8 9 8 8 9 8 7 8 8 8 8 8 9 8 8 8 8 8

420 | 7 9 8 8 8 7 9 8 8 7 8 8 7 8 9 8 8 8 8 8

440 | 7 7 9 8 7 8 9 8 7 8 8 7 8 8 8 7 7 8 8 8

460 | 8 9 8 8 8 7 >9 8 8 8 8 8 7 8 8 >9 8 8 8 8

480 | 7 8 8 8 8 7 8 8 8 8 8 8 8 8 8 8 8 7 8 8

This problem is very neat!

Another thing one could try to find out is wheather there is any lower bound for k(S)..

http://mathoverflow.net/questions/93656/minimal-graphs-with-a-prescribed-number-of-spanning-trees