The extremal spanning-tree conjecture for -free graphs
The extremal spanning-tree conjecture for -free graphs
Let be a prime power and let . For an -vertex -free graph , write for its number of spanning trees, and let denote the maximum of over all such graphs. Let be the orthogonal polarity graph of the projective plane of order . Extremal spanning-tree conjecture.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.