We show that if G is a d–regular graph on n vertices, then the number of spanning forests F (G) satisfies F (G) ≤ dn. The previous best bound due to Kahale and Schulman gave (d+1/2+O(1/d))n. We also have the more precise conjecture that F (G)1/n ≤ (d − 1)d−1 (d2 − 2d − 1)d/2−1 . If this conjecture is true, then the expression on the right hand side is the best possible.

European Journal of Combinatorics

Bencs, F., & Csikvári, P. (2023). Upper bound for the number of spanning forests of regular graphs. European Journal of Combinatorics, 110, 103677:1–103677:12. doi:10.1016/j.ejc.2022.103677