On the Minimal Graph with a Given Number of Spanning Trees
Jiří Sedláček · Canadian Mathematical Bulletin · 1970
LetGbe a finite connected graph without loops or multiple edges. A maximal tree subgraphTofGis called a spanning tree of G. Denote byk(G) the number of all trees spanning the graphG. A. Rosa formulated the following problem (private communication): Letx(≠2) be a given positive integer and denote by α(x) the smallest positive integeryhaving the following property: There exists a graph G onyvertices withxspanning trees. Investigate the behavior of the function α(x).