Paperlane

no. 16 · Tuesday 17 November 2026

The Ferrers bound for spanning trees in bipartite graphs

Boon Suan Ho

math.CO · v2 · 13 pp

Abstract

We prove Ehrenborg's conjecture that every connected bipartite graph $G$ with parts of size $m$ and $n$ has at most $\frac{1}{mn}\prod_{v\in V(G)} \operatorname{deg}(v)$ spanning trees, and that equality holds if and only if $G$ is a Ferrers graph.

comments
simplified proofs, 13 pages
fields
Combinatorics
pdf ↗ page arXiv:2603.17997 ↗