On the number of forests and connected spanning subgraphs

Márton Borbényi, Péter Csikvári, Haoran Luo

Let $F(G)$ be the number of forests of a graph $G$. Similarly let $C(G)$ be the number of connected spanning subgraphs of a connected graph $G$. We bound $F(G)$ and $C(G)$ for regu…