Distinct Spanning Trees 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? 
 A: 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.
