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.


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.

| cite | improve this answer | |
  • $\begingroup$ I hadn't heard of Idoneal numbers before. Thanks for the information and reference. $\endgroup$ – jamisans Feb 24 '14 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.