A Balancing Theorem for Spanning Trees of Rectangular Grid Graphs
This is a theoretical result for mathematicians and computer scientists interested in graph theory and combinatorial enumeration, but it is incremental as it extends known monotonicity properties to a specific class of graphs.
The paper proves that among rectangular grid graphs with a fixed number of vertices, the number of spanning trees increases as the side lengths become more balanced, with the square grid having the maximum number. The result is established via a mathematical proof using the Laplacian product formula and hyperbolic coordinates.
We prove that, among rectangular grid graphs with a fixed number of vertices, the number of spanning trees increases when the side lengths are made more balanced. In particular, among all rectangular grid graphs with $n^2$ vertices, the square $n\times n$ grid has the largest number of spanning trees. The proof starts with the Laplacian product formula, passes to hyperbolic coordinates, and compares logarithms by separating a discrete-concavity term from a positive decreasing residual term.