Physical Sciences and Mathematics Commons^™

A Bound On The Number Of Spanning Trees In Bipartite Graphs, Cheng Wai Koo

HMC Senior Theses

Richard Ehrenborg conjectured that in a bipartite graph G with parts X and Y, the number of spanning trees is at most the product of the vertex degrees divided by |X|⋅|Y|. We make two main contributions. First, using techniques from spectral graph theory, we show that the conjecture holds for sufficiently dense graphs containing a cut vertex of degree 2. Second, using electrical network analysis, we show that the conjecture holds under the operation of removing an edge whose endpoints have sufficiently large degrees.

Our other results are combinatorial proofs that the conjecture holds for …