The Number of Spanning Trees in 4-Regular Simple Graphs

Extending an earlier work by Kostochka for subcubic graphs, we show that a connected graph G with minimum degree 2 and maximum degree 4 has at least 75^n₄/5+n₃/10+1/5 spanning trees, where nᵢ is the number of vertices of degree i in G, unless G is the complete graph on 5 vertices or obtained from the complete graph on 6 vertices by deleting the edges of a perfect matching. This, in particular, allows us to determine the value of the inferior limit of the normalised number of spanning trees (introduced by Alon) over the class of connected 4-regular graphs to be 75^1/5.