Maximum number of spanning trees of a planar graph with a fixed number of edges Let $\mathcal{G}_m$ be the set of planar graphs with exactly $m$ edges. In this question, graphs are allowed to have multiple edges and/or loops.
I want to know what the maximum number of spanning trees of any graph in $\mathcal{G}_m$ is, as a function of $m.$ I suspect this question is too hard to have an exact formula, and so I am also interested in upper bounds for the maximum number of spanning trees of any graph in $\mathcal{G}_m$. 
For small values of $m$, my (possibly incorrect) computations give me the following.


*

*When $m=1$, the maximum number of spanning trees is $1$, realized by any connected graph with $1$ edge.

*When $m=2$, the maximum number of spanning trees is $2$, realized by the graph with two vertices connected by two edges.

*When $m=3$, the maximum number of spanning trees is $3$, realized by a $3$-cycle.

*When $m=4$, the maximum number of spanning trees is $5$, realized by a $3$-cycle with one edge doubled.

*When $m=5$, the maximum number of spanning trees is $8$, realized by a $3$-cycle with two edges doubled or by the complete graph $K_4$ with one edge deleted.

*When $m=6$, the maximum number of spanning trees is $16$, realized by the complete graph $K_4$. 


I could not find anything relevant in OEIS with respect to my computations so far. This is what leads me to believe that an exact formula may not be known.
 A: This is a very, very tough question. It is obvious that for any graph $G$ with $n$ edges the number of spanning trees $t(G)$ does not exceed $2^n$ (each edge is either included in or excluded from a subtree; this is also the upper bound of the number of connected subgraphs of $G$). We can somewhat improve this - if $G$ has $m$ vertices ($m \leqslant n+1$) then we have
$$
t(G) \leqslant \binom{n}{m-1} < 2^n ,
$$
since we need to choose $m-1$ edges out of $n$ (not arbitrarily, of course).
It is a bit easier for the planar graphs but you are correct that the exact formula is not known. I will say more, there is no exact formula even for such a "simple" planar graph as $Z_{n,n}$, which represents $n \times n$ rectangular lattice.
However, there are a few upper and lower bounds, most of them pretty complicated. I suspect there should be an elementary proof for the following conjecture.
Conjecture. For any finite connected planar graph $G$ with $n$ edges we have
$$
t(G) < \tau^n,
$$
where $\tau$ is... say, $1.8$.
Perhaps I am a bit optimistic about 1.8 but there has to be some value of $\tau < 2$ for which an elementary proof exists. I am actually doing some low-tech research into that area right now...
An example: for large values of $n$ it is known that $t(Z_{n,n})$ is pretty close to $\tau^n$, where $\tau = e^{2C/\pi} \approx 1.7916...$, where $C$ is the so-called Catalan constant
$$
C = 1 - 1/3^2 + 1/5^2 - 1/7^2 \pm ...
$$
