The Ferrers bound for spanning trees in bipartite graphs

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)}\mathrm{deg}(v)$ spanning trees, and that equality holds if and only if $G$ is a Ferrers graph. The proof is fully formalized in Lean 4.

14 pages