Create a graph with a specified number of spanning trees

Question

I read that one of the current challenging problems in mathematics is constructing a minimal graph with a specified number of spanning trees (say, $k$).

• However, is there a quick way to create some graph $G$ (not necessarily minimal) that has $k$ spanning trees ?

We can compute the number of spanning trees of a graph $G$ using the pseudo-determinant of the Laplacian matrix of $G$ and the number of labelled vertices (Kirchoff's theorem).

Perhaps answering the following question helps in answering the original question:

• is there a way to generate a Laplacian matrix given its pseudo-determinant value?

Thanks in advance!

Answer 1

A $k$-cycle works if $k>2$. For $k=1$ any tree works. I don't think $k=2$ is possible unless you allow double edges: if the graph is not a tree then it has an $m$-cycle $C$ for some $m>2$; remove edges off $C$ until the graph is connected but has no cycle other than $C$, and then removing an arbitrary edge of $C$ yields at least $m$ spanning trees.

Answer 2

If $G_1$ and $G_2$ are graphs let $G_1 \vee G_2$ denote their wedge sum. That is, $G_1 \vee G_2$ is obtained by taking the one-point union of $G_1$ and $G_2$. It will not matter what vertices we decide to identify. If $G_1$ and $G_2$ have $k_1$ and $k_2$ spanning trees respectively, then $G_1 \vee G_2$ has $k_1k_2$ spanning trees.

As Noam points out a $k$-cycle has $k$ spanning trees for $k \geq 3$. So, we have a graph with $k$ spanning trees on $k$ vertices. When $k$ is composite (with some caveats for the prime $2$) we can quickly do better using the above construction. For example, if we want $k = 9$ we take $K_3 \vee K_3$ which has $5$ vertices instead of $9$.