The Inverse Spanning Tree Problem

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?