Let α(n) be the least number k for which there exists a simple graph with k vertices having precisely n ≥ 3 spanning trees. Similarly, define β(n) as the least number k for which there exists a simple graph with k edges having precisely n ≥ 3 spanning trees. As an n-cycle has exactly n spanning trees, it follows that α(n), β(n) ≤ n. In this paper, we show that α(n) ≤ 1⁄3 (n + 4) and β(n) ≤ 1⁄3 (n + 7) if and only if n /∈ {3, 4, 5, 6, 7, 9, 10, 13, 18, 22}, which is a subset of Euler’s idoneal numbers. Moreover, if n 6≡ 2 (mod 3) and n ≠ 25 we show that α(n) ≤ 1⁄4 (n + 9) and β(n) ≤ 1⁄4 (n + 13). This improves some previously estabilished bounds.