# Create a graph with a specified number of spanning trees

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).

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

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.
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$.
• $k \geq 3$, actually. Also, the proposer explicitly said they don't care about making the graph small, but it's still nice to know this $G_1 \vee G_2$ construction. Note, though, that it doesn't work if one of the factors must be $2$, i.e. for $k$ twice a prime or $k=8$. – Noam D. Elkies Jun 19 '16 at 0:15
• @Noam Thanks. Corrections made. Of course it should be $k \geq 3$ (especially since $k=3$ was used in my example). I figured the OP (and possibly others) might be interested in smaller graphs because of the linked question. – John Machacek Jun 19 '16 at 0:27