# Finding graphs with a given number of spanning trees

All of the graphs considered in this question are connected. We can find the number of spanning trees $t(G)$ of $G$ using Kirchhoff's matrix-tree theorem or the deletion-contraction method. I'm interested in the converse of this problem. That is, given $n$, find $G$ such that $t(G)=n$.

Without some restrictions on $G$ this problem becomes almost trivial. For example, the cycle $C_n$ has $n$ spanning trees. Additionally, if we identify a vertex of graphs $G$ and $H$, the resulting graph has $t(G) \cdot t(H)$ spanning trees. Likewise if we join $G$ and $H$ with any path. So if we could factor $n$ we would just be dealing with the same question for smaller numbers. Thus I would like to restrict $G$ from being a cycle or a graph with a cut-vertex or cut-edge.

My question is then, given $n$, can we always find a graph $G$ which is not a cycle and which has no cut-vertices or cut-edges such that $t(G)=n$? If it is possible to find one, is it possible to find many, or all graphs that satisfy those properties? If it is not possible in general, are we able to determine which $n$ it is true for?

I've gone through all of the relevant graphs up to six vertices from http://www.graphclasses.org/smallgraphs.html and calculated the number of spanning trees for each. The smallest graph which satisfies all of the criteria is $K_4-e$, which has 8 spanning trees. The first ten $n>8$ for which I haven't found a respective $G$ are 9, 10, 13, 18, 22, 25, 33, 37, 42, and 46. All of these numbers are one less than a prime or one less than 2 times a prime.

Thank you.

-
The question by itself is unsolved. You may find this interesting to you as well mathoverflow.net/questions/93656/… and mathoverflow.net/questions/100816/… – Jernej Feb 24 '14 at 17:49
Thanks for your response. I'll take a look at those links and see what I can learn. – jamisans Feb 24 '14 at 19:17

Let $n = pq$ for two numbers $p,q \geq 3.$ Consider the graph $B_{p,q}$ obtained by taking two cycles of length $p$ and $q$ that share a common vertex. Then $t(B_{p,q}) = pq = n.$ Hence for any $n$ that has two divisors $\geq 2$ you can find a graph satisfying your equality. Note that you can generalize this to any number of divisors of $n$ as long as they are all greater than $2.$

The second thing is to consider the theta graph $\Theta_{a,b,c}$ which is the graph obtained by taking three internally disjoint paths of length $a,b$ and $c$ respectively.

It is easy to see that $t(\Theta_{a,b,c}) = ab+ac+bc$ and hence if you can express $n = ab+ac+bc$ for $a \geq 1$ and $b,c \geq 2$ you obtain the desired graph.

It is well known that there are only finitely many numbers $n$ that are not expressible as $n = ab+ac+bc.$ They are called Euler Idoneal numbers.

Hence, for any but a finite number of $n$ you can find a $2$-connected graph satisfying your equality.

More specifically given $n \geq 2$ you can find a $2$-connected graph $G$ that is not a cycle such that $t(G) = n$ if and only if $n \not \in \{3,4,5,6,7,9,10,13,18,22,X \}.$ Where $X$ is an Idoneal number whose existence is not known. See also this paper if you're interested in this problem.

-
I hadn't heard of Idoneal numbers before. Thanks for the information and reference. – jamisans Feb 24 '14 at 20:18