3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.