Fix a natural number $n$. Then a tree on $n$ vertices has $1=n^0$ spanning tree, a cycle on $n$ spanning vertices has $n = n^1$ spanning trees, and the complete graph on $n$ vertices has $n^{n-2}$ spanning trees. These are the extremal trivial cases for what I am considering. Namely, for what natural $1\leq k \leq n-2$ does there exist a graph on $n$ vertices with $n^k$ spanning trees? And if yes, what does the graph look like (in the sense of some sort of characterization)?

I am mainly interested for $n=p$ being an odd prime and $p^{p-3}$ spanning trees. But any known results/approaches would be helpful.

As an aside, it is not difficult to find a graph with $p = 2k+1$ vertices and $p^k$ spanning trees. This is the only non-trivial case that I could figure out.


For $k=1$, use a cycle graph.

Here are solutions for $k\in(2,3,4,5,9,24)$. At the top is $v^k$ as the count of spanning trees, with $v$ as the vertex count.

spanning tree powers

The Petersen graph spanning tree count is $2\times 10^3$.
The Chang graphs spanning tree count is $2 \times 28^{19}$.
The Tietze graph spanning tree count is $5 \times 12^{3}$.
The Gen Quadrangle(2,2) graph spanning tree count is $\frac{15^8}{3}$.

Here are solutions for $k \in (\frac{8}{3}, \frac{10}{3}, \frac{17}{4}, \frac{25}{4}, \frac{31}{4}, \frac{35}{4},\frac{21}{2}, \frac{112}{5}, \frac{116}{3})$.

spanning tree graphs 2

Here are a few graphs with $(p-2) p^{p-3}$ spanning trees.
spanning tree prime

The Paley graphs have $\frac{n-1}{4}^\frac{n-1}{2} \times n^\frac{n-3}{2}$ spanning trees.



Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.