Counting Rooted Spanning Forests in Complete Multipartite Graphs

Abstract

Jin and Liu discovered an elegant formula for the number of rooted spanning forests in the complete bipartite graph \(K_{a_1,a_2}\), with \(b_1\) roots in the first vertex class and \(b_2\) roots in the second vertex class. We give a simple proof of their formula, and a generalization for complete \(m\)-partite graphs, using the multivariate Lagrange inverse.