# Minimal graphs with a prescribed number of spanning trees

**Conjecture**Let be an integer and let denote the least integer such that there exists a simple graph on vertices having precisely spanning trees. Then

Observe that is well defined for since has spanning trees.

The function was introduced by Sedlacek [S] who has shown that for large enough and

Using the fact that almost all positive integers are expressible as for integers it can be shown [A] that for large enough

and otherwise.

Moreover, the only fixed points of are 3, 4, 5, 6, 7, 10, 13 and 22.

The conjecture is motivated by the following graph (ploted for a very small sample of vertices)

The conjecture [C] is justifiable for highly composite numbers since in this case one can construct the graph obtained after taking cycles for every odd prime factor of .

## Bibliography

[S] J. Sedlacek, On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970) 515-517.

[A] J. Azarija, R. Skrekovski, Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees, IMFM preprints 49 (2011) Link to paper

* [C] Minimal graphs with a prescribed number of spanning trees

* indicates original appearance(s) of problem.