The Number of Spanning Trees in 4-Regular Simple Graphs
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_4/5+n_3/10+1/5}$ spanning trees, where $n_i$ is the number of vertices of degree $i$ in $G$, unless $G$ is the complete graph on $5$ …