The extremal spanning-tree conjecture for C4C_4-free graphs

Let qq be a prime power and let n=q2+q+1n=q^2+q+1. For an nn-vertex C4C_4-free graph GG, write τ(G)\tau(G) for its number of spanning trees, and let st(n,C4)\mathrm{st}(n,C_4) denote the maximum of τ(G)\tau(G) over all such graphs. Let ERqER_q be the orthogonal polarity graph of the projective plane of order qq. Extremal spanning-tree conjecture.

st(n,C4)=τ(ERq)=nn32,\mathrm{st}(n,C_4)=\tau(ER_q)=n^{\frac{n-3}{2}},

and the maximizers are precisely the orthogonal polarity graphs. This identifies both the maximum number of spanning trees and all extremal graphs in the prime-power case; the supplied text does not establish whether the conjecture is open or resolved.

Sources & referencesView supporting material

Primary source

András London, “On the Maximum Number of Spanning Trees in C_4-Free Graphs”, arXiv:2602.21639 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.