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