Counting two-forests and random cut size via potential theory

Harry Richman, Farbod Shokrieh, Chenxi Wu

We prove a lower bound on the number of spanning two-forests in a graph, in terms of the number of vertices, edges, and spanning trees. This implies an upper bound on the average c…