Counting k ‐component forests of a graph

We describe an algorithm for computing the number of k ‐component spanning forests of a graph G that runs in polynomial time for fixed k . The algorithm is based on earlier work by Liu and Chow. Our contributions are a simpler graph‐theoretic proof of their formula and a demonstration of how Jacobi's Theorem can be applied to improve the asymptotic time complexity. By matroid duality, the number of connected spanning subgraphs of cyclomatic number c of a planar graph equals the number of c + 1‐component forests in the dual. Thus, one application of this research is an algorithm for counting connected spanning unicyclic subgraphs of a planar graph. We show this can be done in time O(M(n)) , where M(n) is the time complexity of multiplying together two n by n matrices.