On family of graphs with minimum number of spanning trees (Q2637716)

\(\Omega(n,m)\) is the set of all connected simple graphs on \(n\) vertices and \(m\) edges; \(t(G)\) is the number of spanning trees in a graph \(G\); \(v\uplus G\) denotes a graph obtained by joining vertex \(v\) of degree 1 to one of the vertices of \(G\). The author continues a study, when \(k\) is the least integer such that \(m\geq\frac{(n-k)(n-k-1)}2+k\), of certain graphs \(L_{n,m}\) which have figured in his earlier paper [Discrete Math. 309, No. 10, 3074--3082 (2009; Zbl 1202.05021)]. In Theorem 4.5 of that earlier paper the author has proved: Theorem 1.1: Let \(n\) and \(m\) be positive integers so that there is a connected simple graph on \(n\) vertices and \(m\) edges. Then, for any connected graph \(G\) with \(n\) vertices and \(m\) edges, \(t(G)\geq t\left(L_{n,m}\right)\). A family of simple graphs \(\Lambda(n,m)\) (containing \(L_{n,m}\)) is defined recursively using the operation \(\uplus\). The main result of the present paper is: Theorem 3.2: Let \(G\in \Omega(n,m)\). Then \(G\) minimizes the number of spanning trees if and only if \(G\in\Lambda(n,m)\).