Counting Program Seminar Series

The Expected Number of Spanning Trees in Sparse Random Graphs with Given Degrees

Consider a random graph with a given degree sequence. How many spanning trees do you expect it to contain? We calculate an asymptotic formula for the number of spanning trees in the sparse case. Specifically, our result holds when the average degree is large enough to guarantee connectivity and the maximum degree $d_{\max}$ satisfies $d_{max}^4 = o(m-n+1)$, where $n$ is the number of vertices and $m$ is the number of edges in a graph with the given degree sequence. Our proof uses a known asymptotic enumeration formula for the number of graphs with a specified subgraph, and a combinatorial argument that makes use of the Pr{\" u}fer sequence of a tree.