A Tur\'an-type extremal problem for the number of spanning trees in $C_4$-free graphs

Abstract

For a graph \(F\), the Tur\'an 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\H{o}s, R\'enyi and S\'os independently proved that $\ex(n,C_{4})\ge \frac12 q(q+1)^{2}$ for every prime power \(q\), and F\"uredi subsequently established the upper bound $\frac12 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 \(\tau(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$.