Undirected simple connected graphs with minimum number of spanning trees

We show that for positive integers nn, mm with n(n−1)/2≥m≥n−1n(n−1)/2≥m≥n−1, the graph Ln,mLn,m having nn vertices and mm edges that consists of an (n−k)(n−k)-clique and k−1k−1 vertices of degree 1 has the fewest spanning trees among all connected graphs on nn vertices and mm edges. This proves Boesch’s conjecture [F.T. Boesch, A. Satyanarayana, C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004–2009].