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