A Turán-type extremal problem for the number of spanning trees in $C_4$-free graphs

Abstract

For a graph \(F\), the Turán number \(\ex(n,F)\) is the maximum number of edges in an \(F\)-free graph on \(n\) vertices. Let \(q\ge 2\) be an integer and set \(n=q^{2}+q+1\). Brown and Erdős, Rényi and Sós independently proved that $\ex(n,C_{4})\ge \frac12 q(q+1)^{2}$ for every prime power \(q\), and Füredi subsequently established the upper bound $\frac{1}{2}q(q+1{)}^2$ for $\ex(n,C_{4})$ whenever \(q\notin\{1, 7,9,11,13\}\). In this article, we prove that every \(C_{4}\)-free graph \(G\) on \(n\) vertices with at most \(\frac12 q(q+1)^{2}\) edges satisfies $\tau (G)\le n^{(n-3)/2}$, where \(τ(G)\) denotes the number of spanning trees of \(G\). In particular, for every prime power $q\notin \{7,9,11,13\}$, the above upper bound on $\tau (G)$ is attained precisely by the orthogonal polarity graphs, thereby proving London's conjecture for all such $q$.