Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees

summary:Let $\alpha (n)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n \geq 3$ spanning trees. Similarly, define $\beta (n)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n \geq 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha (n),\beta (n) \leq n$. In this paper, we show that $\alpha (n) \leq \frac 13(n+4)$ and $\beta (n) \leq \frac 13(n+7) $ if and only if $n \notin \{3,4,5,6,7,9,10,13,18,22\}$, which is a subset of Euler's idoneal numbers. Moreover, if $n \not \equiv 2 \pmod {3}$ and $n \not = 25$ we show that $\alpha (n) \leq \frac 14(n+9)$ and $\beta (n) \leq \frac 14(n+13).$ This improves some previously estabilished bounds