Distinct Spanning Trees

Question

Say that you are asked to produce a labelled graph $G$ that has $E$ edges and exactly $k$ distinct spanning trees. In general, how much do we know about whether such a graph exists? For example, a labelled graph with $6$ edges and exactly $7$ distinct spanning trees seems to be impossible to create. Beyond brute force/exhaustion, what tools do we have at our disposal to answer questions of this nature?

Answer 1

Take for example the graph $G=(V,E)$ where $V = \{a,b,c,d\}$ and $E = \{ab, bc, bd, cd\}$. Then the adjacency matrix is $$ A = \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ \end{array} \right) $$ and the degree matrix $$ D = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \\ \end{array} \right). $$ Hence the Laplacian matrix is $$ D - A = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \\ \end{array} \right) - \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ \end{array} \right) = \left( \begin{array}{cccc} 1 & -1 & 0 & 0 \\ -1 & 3 & -1 & -1 \\ 0 & -1 & 2 & -1 \\ 0 & -1 & -1 & 2 \\ \end{array} \right). $$ This matrix has eigenvalues $\lambda=4,3,1,0$ and hence by Kirchhoff's theorem it has $\frac14(4\cdot3\cdot 1) = 3$ spanning trees. We can verify this by nothing that a spanning tree of $G$ has as edges $ab$ and exactly two of $bc, bd$, and $cd$, for a total of $\binom 32=3$ spanning trees.

More generally, note that for any tree, $|V|= |E|+1$. Cayley's formula tells us that there are $(|E|+1)^{|E|-1}$ trees on graphs with $|E|$ edges. So the first thing to check would be whether $k>(|E|+1)^{|E|-1}$, in which case no such graph exists. If this inequality does not hold, however, then there is more work to be done.