Square Maximality for Spanning Trees of Induced Grid Subgraphs

Among induced square-lattice graphs on $n^2$ vertices, the $n\times n$ square uniquely maximizes spanning trees.

Background. In 1999, Chung obtained boundary-sensitive estimates for spanning-tree counts in lattice subgraphs [Chu99]. In 2010, Swanepoel proposed on MathOverflow that square shapes should maximize the count at fixed cardinality [Swa10]. Procaccia and Tucker-Foltz recorded the conjecture in the research literature in 2022 [PTF22], and Tapp established general boundary-sensitive grid-graph bounds in 2024 [Tap24]. In 2026, Zhang proved exact balancing for free rectangular grids [Zha26a], then extended the extremal result to pure Cartesian-product families with free and periodic boundary conditions and, in the first version of that paper, formulated the induced-subgraph conjecture for all $d\ge 2$ [Zha26b]. The present note proves the square-maximality conjecture recorded by Procaccia and Tucker-Foltz in 2022, resolving for arbitrary finite induced subgraphs of the square lattice both the question proposed by Swanepoel in 2010 and the two-dimensional case of that original conjecture. Version 2 of [Zha26b] cites this planar result and retains the conjecture for $d\ge 3$.

1 Introduction

Let $\mathcal{L}$ be the infinite square-lattice graph with vertex set ${\mathbb{Z}}^2$. Vertices $x=(x_1,x_2)$ and $y=(y_1,y_2)$ are adjacent when

We call every finite subgraph of $\mathcal{L}$ a square-lattice graph. For a finite graph $G$, write $V(G)$ and $E(G)$ for its vertex and edge sets, and let $\tau (G)$ denote its number of spanning trees. We set $\tau (G)=0$ when $G$ is disconnected and $\tau (G)=1$ when $G$ consists of a single vertex. For a finite set $S\subset {\mathbb{Z}}^2$, let $\mathcal{L}[S]$ be the subgraph induced by $S$, and write

For positive integers $r,s$, set

All logarithms are natural. We use

for Catalan’s constant.

For a graph $H$ in Conjecture 1.1, put $S:=V(H)$. Adding all lattice edges with both endpoints in $S$ produces $\mathcal{L}[S]$, and every spanning tree of $H$ remains a spanning tree of $\mathcal{L}[S]$. Thus

so it suffices to consider induced subgraphs. If $H\ne \mathcal{L}[S]$, adding a missing lattice edge strictly increases the spanning-tree count: adding that edge to any spanning tree of $H$ and deleting one edge from the resulting cycle produces a new spanning tree containing the added edge. We prove the conjecture and characterize equality.

1.1 Outline of the proof

Theorem 1.2 follows from two finite inequalities carrying the same constant: one compares rectangles of different areas, the other compares a set with its rectangular hull.

1. Rectangular area penalty (Lemma 3.1). For positive integers $n,r,s$ with $r\le s$ and $rs\ge n^2$,

   $$\log \tau (r,s)-\log \tau (n,n)\le \frac{4G_{\mathrm{Cat}}}{\pi }(rs-n^2),$$

   with equality only when $r=s=n$. The proof telescopes $\log \tau$ in one side length, drawing on the rectangular product and hyperbolic formulas, the trapezoidal estimate, and the residual bounds of [Zha26a]; the individual references are given in Section 3.

2. Normalized rectangular-hull inequality (Lemma 4.1). Let $S\subset {\mathbb{Z}}^2$, suppose that $\mathcal{L}[S]$ is connected, and suppose that the smallest axis-parallel lattice vertex rectangle containing $S$ is ${\mathrm{\Lambda }}_{r,s}$ after translation. Then

   $$\log \tau (S)-\log \tau (r,s)\le -\frac{4G_{\mathrm{Cat}}}{\pi }|{\mathrm{\Lambda }}_{r,s}\setminus S|.$$

   Interior vacancy components are controlled by planar duality and Tapp’s bound (Theorem 2.1). Boundary-attached vacancies are handled by Lemma 5.1 and the sliding-window and closed-walk arguments in Section 5.

3. Exact matching and square maximality (Theorem 1.2). If $\mathcal{L}[S]$ is connected, $|S|=n^2$, and the smallest axis-parallel lattice vertex rectangle containing $S$ is ${\mathrm{\Lambda }}_{r,s}$, then

   $$|{\mathrm{\Lambda }}_{r,s}\setminus S|=rs-n^2,$$

   and the two inequalities match exactly:

   $$\log \tau (S)-\log \tau (n,n)\le -\frac{4G_{\mathrm{Cat}}}{\pi }(rs-n^2)+\frac{4G_{\mathrm{Cat}}}{\pi }(rs-n^2)=0.$$

   The strictness of the rectangular estimate forces $r=s=n$, after which equality of cardinalities forces $S={\mathrm{\Lambda }}_{n,n}$, up to lattice symmetry.

1.2 Related Work

Kirchhoff’s Matrix–Tree Theorem is the classical starting point for exact spanning-tree enumeration [Kir47]. Square-lattice tree entropy and product formulas have been studied extensively; we use the standard closed-walk evaluation recorded, for example, in [SW00]. Tapp proved boundary-sensitive upper and lower bounds for arbitrary finite grid graphs [Tap24]. The rectangular balancing theorem gives the sharp finite comparison within the free rectangular family [Zha26a], while the product-grid extension studies other boundary conditions and higher-dimensional product families [Zha26b].

Organization. Section 2 fixes notation and records the external inputs. Section 3 proves the rectangular estimate. Sections 4 and 5 prove the normalized hull inequality. Section 6 completes the proof of Theorem 1.2, and Section 7 discusses the argument.

2 Preliminaries and Notation

Empty products and $0\times 0$ determinants are equal to one. The free-boundary constant is

The square-lattice tree entropy is $4G_{\mathrm{Cat}}/\pi$.

For $v\in {\mathbb{Z}}^2$, let ${◻}_v$ be the unit-square graph having $v$ as its bottom-right corner. Following [Tap24, Definition 6], the top-left boundary of a finite square-lattice graph $H$ is

Let $\mathrm{sq}(H)$ denote the number of unit lattice squares whose four boundary edges belong to $H$. Thus $\mathrm{sq}(H)=|V(H)|-|\widehat{\partial H}|$.

We also use two standard facts about spanning trees. First, if $G$ is a connected planar multigraph, let $G^{\star }$ denote its geometric dual, including the exterior dual vertex. Deletion of a primal edge corresponds to contraction of its dual edge, so the cycle matroids of $G$ and $G^{\star }$ are dual. For an edge set $A\subseteq E(G)$, let $G/A$ denote the multigraph obtained by simultaneously contracting the edges of $A$, discarding the resulting loops and retaining parallel-edge multiplicities.

Second, if $T$ is a uniform spanning tree of a connected multigraph $G$ and $F$ is a forest, then

The transfer-current theorem represents this probability as a principal minor of a positive semidefinite kernel [BP93]. Hadamard–Fischer therefore implies that, for an integer $d\ge 1$ and pairwise disjoint edge sets $F_1,\dots ,F_d$ whose union is a forest,

3 Rectangular Area Penalty

We first compare a rectangle whose area is at least $n^2$ with the $n\times n$ square.

4 Normalized Rectangular-Hull Inequality

For a finite nonempty $S\subset {\mathbb{Z}}^2$, define its coordinate extrema by

Its minimal rectangular vertex hull is

Thus, after translation, the hull is ${\mathrm{\Lambda }}_{r,s}$, where $r=x_{+}-x_{-}+1$ and $s=y_{+}-y_{-}+1$. The central estimate is the following.

The proof runs to the end of Section 5. Passing to the planar dual converts the deletion of a set of vertices into the event that a prescribed forest is contained in a uniform spanning tree; the missing vertices are then split into king components, and negative correlation reduces the lemma to one bound per component. Components disjoint from the perimeter are handled below by counting the spanning trees of a union of unit squares in the dual, the rest by the determinant estimate of Section 5.

If $r=1$ or $s=1$, the connectedness of $\mathcal{L}[S]$ and the minimality of the hull imply $S={\mathrm{\Lambda }}_{r,s}$ and $\tau (S)=\tau (r,s)$, so (4.1) is immediate. We assume below that $r,s\ge 2$.

4.1 Dual Contractions

Let $D=R_{r,s}^{\star }$ be the geometric planar dual, including its exterior vertex. If $e\in E(R_{r,s})$, let $e^{\star }$ be its corresponding dual edge. For $X\subseteq {\mathrm{\Lambda }}_{r,s}$, let

and let $H_X$ be the dual subgraph formed by $E_X^{\star }$, with isolated vertices suppressed.

Whenever $\mathcal{L}[{\mathrm{\Lambda }}_{r,s}\setminus X]$ is connected, planar matroid duality gives

Planar tree duality also gives $\tau (D)=\tau (r,s)$. Indeed, deleting the primal edges incident with $X$ leaves the connected graph $R_{r,s}[{\mathrm{\Lambda }}_{r,s}\setminus X]$, together with the isolated vertices of $X$. Its cycle-matroid bases are exactly the spanning trees of the connected component; the isolated vertices contribute no edge choice. Deletion of the primal edges is contraction of their duals.

Call a component nontrivial if it contains at least one edge, and let $F_X$ be a spanning forest of the nontrivial components of $H_X$. Contracting $F_X$ makes every edge of $E_X^{\star }\setminus F_X$ a loop, so the preceding duality identity and the contraction identity give

where $T$ is a uniform spanning tree of $D$.

For $z=(z_1,z_2)\in {\mathbb{Z}}^2$, set $\Vert z{\Vert }_{\mathrm{\infty }}:=max\{|z_1|,|z_2|\}$. Two lattice vertices $u,v$ are king-adjacent when $\Vert u-v{\Vert }_{\mathrm{\infty }}=1$. The perimeter vertex set of the rectangular hull is

Partition ${\mathrm{\Lambda }}_{r,s}\setminus S$ into components for king adjacency. Let $V_{\partial }^{\mathrm{vac}}$ be the union of those components that meet $\partial {\mathrm{\Lambda }}_{r,s}$, and denote the remaining, interior components by

Here $m$ may be zero. For a primal vertex $v$, call the subgraph formed by the duals of the primal edges incident with $v$ its dual face-star. Distinct king components have disjoint dual edge sets. Two primal vertices can be incident with a common bounded unit face only if their ${\ell }^{\mathrm{\infty }}$-distance is at most one; their dual face-stars are therefore vertex-disjoint, except that different boundary components can share the exterior dual vertex. Within one king component, the face-stars of successive vertices meet, so their union is connected; for a boundary component, one of these stars also meets the exterior vertex. Hence $H_{V_{\partial }^{\mathrm{vac}}}$ is connected when $V_{\partial }^{\mathrm{vac}}\ne \varnothing$, and each $H_{J_i}$ is connected. Set $F_{V_{\partial }^{\mathrm{vac}}}=\varnothing$ when $V_{\partial }^{\mathrm{vac}}=\varnothing$; otherwise choose a spanning tree of $H_{V_{\partial }^{\mathrm{vac}}}$. For $1\le i\le m$, choose a spanning tree $F_{J_i}$ of $H_{J_i}$. These forest edge blocks are pairwise disjoint, and their union is a spanning forest of the nontrivial components of $H_{{\mathrm{\Lambda }}_{r,s}\setminus S}$.

We record why all deletion graphs used here are connected. Every king component $C$ has a nearest-neighbour edge to $S$: on a nearest-neighbour path from $C$ to $S$, the first vertex outside $C$ cannot lie in another king component. Moreover, a diagonal king step between $u,v\in C$ can be replaced by a two-edge nearest-neighbour path through an orthogonal corner of their unit square. If the corner is in ${\mathrm{\Lambda }}_{r,s}\setminus S$, it is king-adjacent to $u$ and hence belongs to $C$; otherwise it belongs to $S$. Thus $\mathcal{L}[S\cup C]$ is connected. It follows that every undeleted king component is joined to the common connected subgraph $\mathcal{L}[S]$. Hence $\mathcal{L}[{\mathrm{\Lambda }}_{r,s}\setminus V_{\partial }^{\mathrm{vac}}]$ and every $\mathcal{L}[{\mathrm{\Lambda }}_{r,s}\setminus J_i]$ are connected.

Applying (4.2) and (2.1) to the disjoint forest edge blocks gives

The factor indexed by $V_{\partial }^{\mathrm{vac}}$ is one when $V_{\partial }^{\mathrm{vac}}=\varnothing$.

4.2 Interior Vacancy Components

For each $i\in \{1,\dots ,m\}$, put $J:=J_i$. The following argument is vacuous when $m=0$. The dual graph $H_J$ is a finite connected square-lattice graph. Every $v\in J$ contributes a complete unit square to $H_J$, formed by the four duals of the primal edges incident with $v$. Different vertices give different squares, so

By Theorem 2.1,

For every spanning tree $F$ of $H_J$, (4.2) gives

These events are pairwise incompatible: the union of two distinct spanning trees on the same vertex set contains a cycle, while $T$ is acyclic. Summing over the spanning trees of $H_J$ therefore gives

which with the preceding consequence of Tapp’s theorem yields

The argument used that $J$ misses the perimeter: only then does each $v\in J$ have four incident primal edges, whose duals close into a unit square. A vacancy on $\partial {\mathrm{\Lambda }}_{r,s}$ has fewer, so the count above does not apply to it, and the same exponential factor for the union $V_{\partial }^{\mathrm{vac}}$ of the boundary-attached components is obtained differently, in Section 5.

5 Boundary-Attached Vacancies

What is proved here is a comparison of two determinants. Both $\tau (r,s)$ and $\tau ({\mathrm{\Lambda }}_{r,s}\setminus V_{\partial }^{\mathrm{vac}})$ have the form $det(4I-\mathsf{A})$ for the adjacency matrix of a set of unit faces, and expanding $\log det$ in closed walks turns their ratio into a sum, over closed walks, of the number of placements meeting a face with a corner in $V_{\partial }^{\mathrm{vac}}$. The first three subsections bound that number by $|V_{\partial }^{\mathrm{vac}}|$ plus a multiple of the number of vacancy runs interior to a row or column; the last assembles the estimate.

Retain the boundary-vacancy set $V_{\partial }^{\mathrm{vac}}\subseteq {\mathrm{\Lambda }}_{r,s}\setminus S$ from the preceding section. For $z\in {\mathbb{Z}}^2$ and $A\subseteq {\mathbb{Z}}^2$, define the translate

Let

index the unit faces of $R_{r,s}$. The face indexed by $z\in \mathrm{\Phi }$ has corner set $z+\{0,1{\}}^2$. Define the marked and unmarked face sets by

An interval component is a maximal nonempty set of consecutive integers. Let ${\rho }_x$ be the total number of interval components of ${\mathrm{\Lambda }}_{r,s}\setminus V_{\partial }^{\mathrm{vac}}$ in all horizontal rows, and let ${\rho }_y$ be the corresponding total in all vertical columns. Put

Every row and column contains a vertex of $S$. Indeed, minimality gives a vertex of $S$ on each of the two extreme columns, and a nearest-neighbour path in $S$ between them visits every intermediate column. The row statement is identical. Consequently $g_x,g_y\ge 0$. Here a run of $V_{\partial }^{\mathrm{vac}}$ is an interval component of $V_{\partial }^{\mathrm{vac}}$ in a row or column, and it is internal when it touches neither endpoint of that row or column. Then $g_x$ is exactly the total number of horizontally internal runs of $V_{\partial }^{\mathrm{vac}}$, and $g_y$ is the corresponding number of vertically internal runs.

5.1 One-Dimensional Windows

We begin with an elementary interval estimate.

For an integer $p$ with $0\le p\le r-1$, define

Applying Lemma 5.1 in each row gives

5.2 A Sliding-Window Injection

For an integer $x$ with $0\le x\le r-1-p$, let

The second ingredient is

It is proved in two steps: each internal interval component of $Y_{p,x}$ contains the projection of a connected piece of vacancy runs lying in the window and carrying no run that touches row $0$ or row $s-1$; and those pieces, taken over all windows, inject into the vertically internal runs of $V_{\partial }^{\mathrm{vac}}$.

To prove it, form the full run graph, whose vertices are the maximal vertical runs of $V_{\partial }^{\mathrm{vac}}$. Join two runs in adjacent columns when their integer intervals overlap or are adjacent, and mark a run if it touches row $0$ or row $s-1$. The connected components of the full run graph are precisely the king components of $V_{\partial }^{\mathrm{vac}}$. Since every such component meets $\partial {\mathrm{\Lambda }}_{r,s}$, it contains either a marked run or a run in column $0$ or $r-1$.

Fix once and for all a rooted spanning tree in every component of the full run graph. Use a marked run as the root whenever possible, and otherwise use a run in column $0$ or $r-1$. For the window of columns $[x,x+p]$, consider the subgraph of the full run graph induced by the run vertices whose columns lie in this window. In each of its components containing no marked run, choose a run of minimum depth, where depth is measured in the previously fixed rooted tree.

If the chosen run is not the root, its parent lies outside the window; otherwise the parent would belong to the same induced component at a smaller depth. Parent and child lie in adjacent columns. If the parent is to the left, then $x$ is the child’s column; if the parent is to the right, then $x$ is the child’s column minus $p$. Thus the oriented parent–child pair determines the window start uniquely. If the chosen run is an unmarked root, column $0$ forces $x=0$, while column $r-1$ forces $x=r-1-p$. Therefore the pairs

inject into the unmarked vertices of the full run graph. These vertices are exactly the vertically internal runs of $V_{\partial }^{\mathrm{vac}}$, of which there are $g_y$.

Every internal interval component of $Y_{p,x}$ contains the vertical projection of an induced run-graph component containing no marked run. The projection of a connected induced run-graph component is itself an integer interval, because adjacent runs overlap or are one unit apart. Distinct interval components therefore contain distinct such induced components. This proves (5.2).

For integers $a,b$ with $1\le a\le r$ and $1\le b\le s$, define

Applying Lemma 5.1 vertically and then using (5.1) and (5.2) gives, for every integer $q$ with $0\le q\le s-1$,

5.3 Closed-Walk Charging

For an integer $\ell \ge 1$, put $e_1=(1,0)$ and $e_2=(0,1)$. A closed step word of length $\ell$ is a sequence

Define its partial-sum set by

and set

Let ${\mathcal{C}}_{\ell }$ be the set of closed words of length $\ell$, and put $w_{\ell }=|{\mathcal{C}}_{\ell }|$.

We use two exact closed-walk sums. The first is the standard square-lattice tree-entropy identity [SW00]:

This series is absolutely convergent: $w_{2a}={(\genfrac{}{}{0ex}{}{2a}{a})}^2$ for $a\ge 1$, so its nonzero terms are $O(a^{-2})$. The second is

We include the proof of (5.5). Let $a\ge 1$ and $h=2a$. A one-dimensional bridge of length $h$ is a sequence $\gamma =({\gamma }_0,\dots ,{\gamma }_h)$ such that ${\gamma }_0={\gamma }_h=0$ and ${\gamma }_t-{\gamma }_{t-1}\in \{-1,1\}$ for $1\le t\le h$. Define

Thus $\mathrm{span}(\gamma )+1$ is the number of integer levels visited by $\gamma$. For an integer $k>0$ and a bridge that visits $k$, let ${\sigma }_k$ be its first visit to $k$, and set

This reflection is a bijection with unrestricted walks of length $h$ from $0$ to $2k$. The negative levels are symmetric, while level zero is visited by every bridge. Summing over levels rather than over bridges,

For even $\ell$, condition a two-dimensional closed word on the even number $h$ of its horizontal steps and on their positions. Write $[{\zeta }^0]$ for extraction of the constant term in the formal variable $\zeta$. The bridge identity is also immediate when $h=0$. Using it gives

There are no closed words for odd $\ell$. For $|t|<1/4$, define

At $t=\pm 1/4$, its terms are $O({\ell }^{-3/2})$, so both boundary series converge. Abel’s theorem extends the displayed closed form to both endpoints, applied to $\mathcal{B}(-t)$ for the negative endpoint. Taking the even part gives

which proves (5.5).

Define

Its bounding face rectangle has $r_x(\omega )+1$ face columns and $r_y(\omega )+1$ face rows. The corresponding primal vertex window has $r_x(\omega )+2$ columns and $r_y(\omega )+2$ rows and meets $V_{\partial }^{\mathrm{vac}}$. For fixed $\omega$, translation by its coordinatewise minima makes the map from a start $z$ to this window’s lower-left corner injective. If either span is too large for $\mathrm{\Phi }$, there is no admissible start and the desired estimate is immediate. Otherwise, taking $p=r_x(\omega )+1$ and $q=r_y(\omega )+1$ in (5.3) yields

5.4 The Determinant Estimate

Recall that $M$ and $U=\mathrm{\Phi }\setminus M$ are respectively the marked and unmarked face sets. Every face in $M$ belongs to a face-star indexed by $V_{\partial }^{\mathrm{vac}}$. Since every king component of $V_{\partial }^{\mathrm{vac}}$ meets the boundary, contraction of $E_{V_{\partial }^{\mathrm{vac}}}^{\star }$ joins all these face vertices to the exterior dual vertex. On the other hand, a face indexed by $U$ has no corner in $V_{\partial }^{\mathrm{vac}}$, so all four primal boundary edges remain. Thus the bounded faces of $R_{r,s}[{\mathrm{\Lambda }}_{r,s}\setminus V_{\partial }^{\mathrm{vac}}]$ are exactly those indexed by $U$.

For $Y\subseteq \mathrm{\Phi }$, let ${\mathsf{A}}_Y$ be the adjacency matrix of the face-grid graph induced by $Y$, and let $I$ denote the identity matrix of the appropriate order. Rooted planar duality and the Matrix–Tree Theorem [Kir47] give

Primal bridges become dual loops and do not affect the determinant. When $U=\varnothing$, the second determinant is the $0\times 0$ determinant and equals one.

The horizontal edges of ${\mathrm{\Lambda }}_{r,s}\setminus V_{\partial }^{\mathrm{vac}}$ number $|{\mathrm{\Lambda }}_{r,s}\setminus V_{\partial }^{\mathrm{vac}}|-{\rho }_x$, and the vertical edges number $|{\mathrm{\Lambda }}_{r,s}\setminus V_{\partial }^{\mathrm{vac}}|-{\rho }_y$. Therefore

Since the graph is connected, Euler’s formula, together with $g_x={\rho }_x-s$, $g_y={\rho }_y-r$, and $|\mathrm{\Phi }|=(r-1)(s-1)$, gives

and therefore

The spectral radius of the rectangular face adjacency is

Since ${\mathsf{A}}_U$ is a principal submatrix, its spectral radius is also below $4$, with the empty matrix assigned spectral radius zero. Hence, for $Y\in \{\mathrm{\Phi },U\}$, the matrix trace $\mathrm{tr}$ satisfies

Both log-determinant series are absolutely convergent by the preceding spectral-radius bound.

The trace difference counts precisely the closed-walk starts in $\mathrm{\Phi }$ whose walk meets $M$:

All terms used below are nonnegative, and (5.4)–(5.5) show that the dominating series are finite. Thus Tonelli’s theorem justifies the ensuing interchanges of sums. Subtract the two instances of (5.9), substitute (5.10), and apply the charging bound (5.6). Evaluating the three resulting series by (5.4) and (5.5), the $g_y$ term by symmetry between the coordinates, and then inserting (5.8) and the identifications (5.7), gives

We have proved the boundary factor

6 Proof of Square Maximality

7 Discussion

The rectangular area penalty bounds the gain available from enlarging the hull, and the normalized hull inequality charges every omitted vertex by exactly the same entropy constant. In log-difference form the two estimates add, their constants cancel, and strictness comes entirely from the rectangular estimate.

Current task statement

Let \(\mathcal L\) be the standard nearest-neighbor square-lattice graph with vertex set \(\mathbb Z^2\): distinct vertices \(x,y\in\mathbb Z^2\) are adjacent exactly when \(\|x-y\|_1=1\). For a finite set \(S\subset\mathbb Z^2\), let \(\mathcal L[S]\) be the induced subgraph. For a finite connected graph \(G\), let \(\tau(G)\) denote its number of spanning trees. Set \(\tau(G)=0\) when \(G\) is disconnected. Let

  \[
  Q_n=P_n\square P_n=\mathcal L[\{0,1,\ldots,n-1\}^2]
  \]

be the \(n\times n\) square grid graph, which has \(n^2\) vertices.

Resolve the following conjecture completely in dimension two:

SQUARE-MAXIMALITY THEOREM. For every integer \(n\ge 1\) and every finite set \(S\subset\mathbb Z^2\) with \(|S|=n^2\),

  \[
  \tau(\mathcal L[S])\le \tau(Q_n).
  \]

Moreover, equality holds if and only if \(S\) is an \(n\times n\) lattice square, up to an automorphism of the square lattice; equivalently, up to translation, reflections, and interchange of the two coordinates.

The disconnected case is immediate under the convention \(\tau=0\), so the substantive case is that \(\mathcal L[S]\) is connected. The theorem must cover arbitrary connected induced subgraphs. Shapes may be nonconvex, have holes, have cutvertices or bridges, have disconnected intersections with individual rows or columns, and have long tentacles.

REQUIRED BACKGROUND

Read the following two papers in full before committing to a proof route:
  1. https://arxiv.org/abs/2605.23773
  2. https://arxiv.org/abs/2606.24016v1

Treat their proved theorems as available background, with precise citation and hypothesis checking. In particular:
  - For rectangular grids, if \(AB=ab\) and \(A\le a\le b\le B\), the first paper proves

  \[
  \log\tau(P_a\square P_b)-\log\tau(P_A\square P_B) \ge \operatorname{arsinh}(1)\bigl((A+B)-(a+b)\bigr),
  \]

with strict inequality unless the two rectangles agree. Consequently, \(Q_n\) is already the unique maximizer among rectangular grids with \(n^2\) vertices.
  - The second paper proves the analogous perfect-power result within pure Cartesian-product families and states the induced-subgraph conjecture above as its \(d=2\) case.
  - Every connected induced \(n^2\)-vertex lattice subgraph satisfies

  \[
  |E|\le 2n(n-1), \qquad |E|-|V|+1\le (n-1)^2,
  \]

with equality only for \(Q_n\). These edge-count and cycle-rank facts are useful but are explicitly too coarse by themselves.
  - The product-spectrum and hyperbolic-residual arguments in the papers rely essentially on Cartesian-product structure. Do not silently extend them to arbitrary induced subgraphs without a new comparison theorem and complete error control.

You may use standard results such as Kirchhoff's Matrix-Tree Theorem, the weighted matrix-tree theorem, Rayleigh monotonicity, the transfer-current theorem, Wilson's and Aldous-Broder algorithms, planar duality for spanning trees, Schur complements, determinant identities, Cauchy-Binet, and standard majorization or rearrangement theorems. Every invoked result must nevertheless be stated precisely enough that its hypotheses and the direction of its implication can be audited.

For this benchmark, work under the premise that an exact affirmative finite proof is available to be found. A response that only labels the conjecture open, difficult, plausible, asymptotically supported, or computationally verified is not responsive. If exact integer calculations produce a genuine counterexample, that supersedes the premise and gives a complete negative resolution; approximate numerical evidence does not.

The finished argument must establish the stated theorem for every \(n\ge1\), including all equality cases. It may not impose extra conditions such as simple connectivity, orthogonal convexity, row- or column-convexity, bridgelessness, bounded aspect ratio, or product structure.

WHAT DOES NOT COUNT

Intermediate advances are useful internally, but the delivered solution must settle the whole theorem. None of the following, standing alone, is an acceptable endpoint:
  - proving only the rectangular, Ferrers, Young-diagram, convex, simply connected, or hole-free cases;
  - proving an asymptotic inequality, an inequality only up to \(e^{o(n^2)}\), or a statement only for sufficiently large \(n\);
  - observing that the square minimizes boundary or maximizes edges, average degree, face count, or cycle rank;
  - applying a general upper bound on \(\tau(G)\) that remains above \(\tau(Q_n)\);
  - asserting without proof that a compression, symmetrization, hole-filling operation, or boundary-vertex transfer increases the number of spanning trees;
  - reducing the theorem to a new lemma that is equivalent or nearly equivalent in strength, without proving that lemma;
  - proving a comparison for one eigenvalue or a few spectral moments while the full determinant comparison remains missing;
  - computational verification through any fixed \(n\), or floating-point determinant comparisons;
  - omitting strictness or the equality case;
  - invoking a theorem whose hypotheses fail for induced lattice subgraphs with holes, bridges, cutvertices, or nonsimple planar duals.

MULTIAGENT RESEARCH MANAGEMENT

Exploit multiagent v2 at full scale, coordinating as many as 64 simultaneous agents when useful. Allocate agents adaptively rather than reserving a predetermined number for each strategy. Launch the search with a broad collection of mathematically independent directions. In the early stages, keep the leading hypothesis private from most agents so that the group does not collapse onto one seductive but incomplete route. The initial collection should span genuinely different mechanisms, including:
  - Minimal-counterexample and structural induction. Try to prove that an extremizer has no holes, no bridges, interval row or column sections, orthogonal convexity, or some other structure that eventually forces a rectangle.
  - Lattice-specific compressions and local vertex transfers. Derive exact determinant or effective-resistance formulas for moving an exposed vertex into a concavity while preserving cardinality, connectedness, and inducedness.
  - Grounded-Laplacian determinant comparison. Explore Schur complements, rank-one or low-rank updates, log-determinant inequalities, Gaussian-free-field integral representations, and weighted interpolations between shapes.
  - Heat-trace or spectral-zeta comparison. Seek a valid rearrangement inequality strong enough to integrate to the determinant, while explicitly testing whether pointwise heat-trace domination is even true.
  - Planar methods. Explore dual spanning trees, deletion-contraction in the primal and dual, the Temperley bijection, Kasteleyn determinants, dimers, electrical networks, and face-by-face transformations, with explicit treatment of holes and bridges.
  - Uniform-spanning-tree and random-walk methods. Explore Wilson and Aldous-Broder, transfer currents, loop-erased random walk, and a sharp extension of Tapp's multiplier and escape-probability framework.
  - Graphic-matroid and tree-polynomial methods. Explore basis-generating polynomials, strong log-concavity, negative dependence, injections between spanning-tree sets, and lattice-aware edge-exchange maps.
  - Extremal graph theory constrained by the lattice. Explore degree sequences, planar embeddings, block decompositions, and bounds that exploit lattice geometry rather than merely maximum degree.
  - Exact computation for discovery and falsification. Enumerate small lattice animals up to translation and lattice symmetry, compute \(\tau\) by exact integer determinants, test proposed local moves, and locate the first failure of every candidate sublemma.

Regard this as a menu of independent research programs, not as an indication that one route is intended. Sustain several mutually incompatible proof architectures over multiple rounds.

Two especially clean possible endgames are:
  1. Construct a finite sequence of shape operations that preserves the admissible class, never lowers \(\tau\), is strictly improving away from a square, and terminates at \(Q_n\).
  2. Prove a direct determinant or tree-count inequality valid for every admissible \(S\), with equality precisely at \(Q_n\).

Any other fully rigorous architecture is equally valid.

Keep a live research ledger indexed by genuine mathematical mechanism. Each entry should record:
  - the key statement in fully quantified form;
  - the exact role that statement would play in a complete proof;
  - every hypothesis on which it depends;
  - exact computational experiments already run;
  - counterexamples to natural stronger versions;
  - the narrowest unresolved step;
  - a status tag such as active, blocked, disproved, or merged.

Classify routes by mathematical content rather than cosmetic differences in presentation. When too many agents cluster around one idea, move some of them to neglected directions. Elegance of a reduction is not evidence of completion: a route that merely renames the main difficulty as a “compression theorem,” “rearrangement principle,” or “extremal-domain lemma” has made little progress until that statement is proved. If a program reaches a missing lemma essentially as hard as the original theorem, freeze that program. Resume it only after a new invariant, construction, exact identity, or induction mechanism appears.

Delay cross-fertilization until independently developed routes are mature enough that their actual advantages and defects are visible. Demand mathematical artifacts from every agent: complete lemma proofs, exact formulas, determinant quotients, resistance estimates, explicit tree maps, certified counterexamples to subsidiary claims, or finite certificates that another agent can check. Discard vague progress summaries, unsupported confidence, continuum analogies with no finite discretization, and assertions that a global compatibility step is automatic.

All computational evidence used in reasoning must be exact. Suitable tools include fraction-free Bareiss elimination, symbolic determinants, and independently reproduced integer Matrix-Tree calculations. Use computation to reveal patterns and destroy false claims, not as a substitute for the uniform proof. Archive the coordinates and exact tree counts of every shape that refutes a proposed local rule.

ADVERSARIAL AUDIT REQUIREMENTS

Maintain dedicated skeptical review throughout the search. Every prospective proof must survive checks for the following errors:
  - confusing a vertex set in \(\mathbb Z^2\) with a polyomino made of unit cells, thereby shifting the graph or miscounting vertices, faces, or boundary;
  - inferring a tree-count comparison from boundary size or edge count when the graphs are not nested;
  - invoking Rayleigh monotonicity without a valid common network and an actual conductance increase;
  - using a vertex relocation that changes cardinality, breaks connectedness, fails to produce an induced subgraph, leaves an isolated component, or has no well-founded termination measure;
  - comparing cofactors based on inconsistent roots or vertex identifications;
  - dropping the Laplacian zero mode, the Matrix-Tree normalization, or a sign in a determinant or heat-kernel integral;
  - asserting coordinatewise eigenvalue order or spectral majorization rather than proving it;
  - using planar duality while ignoring bridges, dual loops, parallel dual edges, holes, the unbounded face, or disconnected collections of faces;
  - proposing a combinatorial tree map without a complete proof of well-definedness and of injectivity or surjectivity as required;
  - establishing weak monotonicity but leaving unexplained nonsquare equality cases;
  - replacing the target by an equivalent “domain monotonicity,” “compression,” or “entropy” assertion and treating that assertion as known;
  - using an asymptotic expansion to decide finite changes whose logarithmic gain can stay bounded;
  - relying on computed positivity without a symbolic estimate uniform in \(n\).

Every proposed geometric move must come with a full certificate containing:
  1. its precise definition on lattice vertex sets;
  2. preservation of \(|S|\) and of the induced-subgraph interpretation;
  3. preservation of connectedness, or a complete analysis of any exceptional case;
  4. an exact formula for the resulting tree-count ratio or difference;
  5. a proof of its sign in every allowed configuration;
  6. the full characterization of equality;
  7. a well-founded quantity that guarantees termination;
  8. proof that terminal configurations are exactly the squares, or a justified final passage to the established rectangular theorem.

Every determinant, spectral, or heat-kernel route must supply:
  1. the precise matrices or operators;
  2. a common ambient space, or a rigorous embedding or intertwining construction;
  3. correct handling of the zero eigenvalue and all normalization factors;
  4. a proved Loewner, majorization, trace, or integral comparison with the needed orientation;
  5. convergence and endpoint estimates for all integral formulas;
  6. equality conditions propagated through every step.

The coordinating agent should repeatedly combine results, attack them, redirect effort, and initiate further rounds. A failed opening round is not a stopping condition. Once a serious lemma emerges, send independent agents to seek separate proofs, construct exact counterexamples, analyze equality, and test whether the lemma merely restates the target. Retain multiple distinct routes until one closes the entire argument.

Before endorsing a proof, commission a clean-room review by agents who did not build it. They must reconstruct the dependency graph, verify citations and algebra, test local assertions on exact small examples, and actively try to break the proof. Correct all defects and repeat this review until no gap remains.

FINAL-ANSWER REQUIREMENTS

Return a self-contained, publication-quality mathematical proof, not a research diary. The final response must:
  - state the theorem precisely;
  - define all notation;
  - state and prove every new lemma in dependency order;
  - identify precisely which results are cited from the two supplied papers or standard literature;
  - prove the inequality for every \(n\ge1\);
  - separately prove the equality characterization;
  - include exact finite verification only where genuinely needed for finitely many base cases;
  - contain no unsupported “clearly,” “routine,” or “by symmetry” at a substantive step;
  - contain no appeal to the multiagent process, numerical evidence, or the premise that a proof exists.

Failure of the current collection of ideas is not a reason to terminate. Start additional rounds and revisit frozen routes only when a substantively new device appears. Deliver the main answer only after a complete argument has passed the independent audit.

If a nonnegotiable execution limit interrupts the investigation, never disguise a conjectural chain as a proof. Report only rigorously established lemmas, exact failures of attempted routes, and a single precisely formulated outstanding obstacle, all clearly marked incomplete. This is an emergency fallback, not a chosen endpoint.

Allocate no less than eight hours of sustained search before considering termination. Internet lookup is permitted for the two supplied papers, routine background, and standard named results. Do not use web search to hunt for a preexisting solution to this exact benchmark, and do not substitute an “open problem” report for the requested investigation.

Please build upon these initial results and resolve the conjecture. Aim for a breakthrough and consider a diverse set of approaches, not limited by previous work. Please try for at least 8 hours before returning an incomplete result.