Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
The authors establish a tight upper bound of $\tau(G) \le n^{(n-3)/2}$ on the number of spanning trees for any $C_4$-free graph on $n = q^2+q+1$ vertices with at most $\frac{1}{2}q(q+1)^2$ edges. For all prime powers $q \notin \{7, 9, 11, 13\}$, this maximum is uniquely attained by orthogonal polarity graphs derived from finite projective planes. This result resolves London's longstanding conjecture for nearly all prime-power orders and closes a key open problem in Turán-type graph enumeration.
Orthogonal polarity graphs uniquely maximize spanning tree complexity under girth-4 constraints, proving London's conjecture for almost all prime-power orders.
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 $\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 $τ(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 $τ(G)$ is attained precisely by the orthogonal polarity graphs, thereby proving London's conjecture for all such $q$.