# P2676: Most spanning trees in a 10-regular circulant on 101 vertices

- ID: `P2676`
- Reference: `circulant-spanning-trees-101-degree10`
- Page: https://theoremdb.org/statements/P2676
- Record maturity: Reviewed problem with recorded work

## Problem

For \(S\subseteq\{1,\ldots,50\}\) with \(|S|=5\), let \(G_S=\operatorname{Cay}(\mathbb Z_{101},\{\pm s:s\in S\})\). Determine \(\max_S\tau(G_S)\), the largest number of spanning trees.

### Problem setup

- **Remark.** Every G_S is a simple 10-regular undirected circulant graph.
- **Definition.** tau(G) denotes the number of spanning trees.

### What counts as a solution

- Give a step set attaining the maximum, its exact tree count, and a complete symmetry-reduced sweep with exact replay of every contender.

## The answer

An exact sweep of 42,376 signed-unit orbits proves that S={1,15,18,22,27} uniquely maximizes the tree count up to Cayley isomorphism. [1](#reference-1)

**Review status:** Reproduced.

**Lean verification:** not Lean-verified.

### Verification

Let
\[
S_*=\{1,15,18,22,27\}.
\]
Exact enumeration gives
\[
\max_{|S|=5}\tau(G_S)=
2708274425686971438523646018073797918175286202944373217379948692092215150697249050994964490229261.
\]
Multiplication by 4 modulo 101, followed by replacing residues above 50 with their negatives, sends \(S_*\) to
\[
\{4,7,13,29,41\}.
\]
Thus the sampled incumbent in the candidate record already attained the maximum.

The group \((\mathbf Z/101\mathbf Z)^\times/\{\pm1\}\) has order 50 and acts on the five-element step sets. The \(\binom{50}{5}=2{,}118{,}760\) sets split into 42,376 orbits: 42,375 orbits of size 50 and one orbit of size 10. The exact search finds one maximizing orbit. The next orbit is represented by \(\{7,15,16,18,28\}\), with tree count
\[
2705790677807473137809613684625587492780256938436447544415672932035143210140285775448737562551029.
\]
Every step is nonzero modulo the prime 101, so each graph in the search is connected.

## Work

### Proof and evidence for the resolution

**Computation 1 (The exact maximum has 97 digits).** An exact sweep of 42,376 signed-unit orbits proves that S={1,15,18,22,27} uniquely maximizes the tree count up to Cayley isomorphism.

Let
\[
S_*=\{1,15,18,22,27\}.
\]
Exact enumeration gives
\[
\max_{|S|=5}\tau(G_S)=
2708274425686971438523646018073797918175286202944373217379948692092215150697249050994964490229261.
\]
Multiplication by 4 modulo 101, followed by replacing residues above 50 with their negatives, sends \(S_*\) to
\[
\{4,7,13,29,41\}.
\]
Thus the sampled incumbent in the candidate record already attained the maximum.

The group \((\mathbf Z/101\mathbf Z)^\times/\{\pm1\}\) has order 50 and acts on the five-element step sets. The \(\binom{50}{5}=2{,}118{,}760\) sets split into 42,376 orbits: 42,375 orbits of size 50 and one orbit of size 10. The exact search finds one maximizing orbit. The next orbit is represented by \(\{7,15,16,18,28\}\), with tree count
\[
2705790677807473137809613684625587492780256938436447544415672932035143210140285775448737562551029.
\]
Every step is nonzero modulo the prime 101, so each graph in the search is connected.

### Background and intake notes

The entire search has about two million five-subsets, and each completed block has a short spectral checksum.

- Original intake status: Status remains unverified. Extremal spanning-tree counts for circulants are studied, and this parameter may be computationally accessible.
- Rank all 2118760 step sets by Fourier eigenvalue products, then recompute contenders with an exact Laplacian cofactor. Quotient multiplication by units and sign.
- Trap: floating eigenvalue products can misorder close contenders. Matrix-tree division by 101 must be handled exactly.

- Recorded example: The sampled incumbent uses S={4,7,13,29,41}.

### Supporting results

- **Theorem 1** (established): Matrix-Tree eigenvalue products modulo six 61-bit primes reconstruct every integer count without floating-point comparisons. [1](#reference-1)

### Prior approaches

- **Route 1** (supported): The literature gives exact formulas and asymptotic extremal results; the particular 42,376-orbit comparison appears to be a new finite computation. [2](#reference-2) [4](#reference-4) [3](#reference-3) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python visits all 2,118,760 step sets, computes one exact count per orbit, and hashes the full canonical result table.
- **Artifact 2** (reproduced): Fraction-free Bareiss elimination of a 100 by 100 Laplacian minor reproduces the 97-digit maximum. [1](#reference-1)

### Computational notes

- One hundred thousand seeded step sets were ranked by double-precision Fourier log products. Exact Bareiss elimination of a 100 by 100 Laplacian minor for the best set gave 2708274425686971438523646018073797918175286202944373217379948692092215150697249050994964490229261 spanning trees.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `circulant-spanning-trees-101-degree10`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## Lean verification

An informal proof is recorded. A Lean formalization still needs to be attached.

[Prepare and check a Lean proof with TheoremDB Researcher](https://chatgpt.com/g/g-6a6c206c5acc8191b184bb55fb72c5b3-theoremdb-researcher?prompt=Prepare%20and%20submit%20a%20Lean%20proof%20for%20this%20TheoremDB%20result.%0A%0AExact%20problem_ref%3A%20circulant-spanning-trees-101-degree10%0A%0AExact%20title%3A%20Most%20spanning%20trees%20in%20a%2010-regular%20circulant%20on%20101%20vertices%0A%0ACanonical%20packet%3A%20https%3A%2F%2Ftheoremdb.org%2Fstatements%2Fcirculant-spanning-trees-101-degree10%2F%23lean-verification%0A%0AStart%20with%20prepareLeanProof%20for%20this%20exact%20problem_ref.%20Use%20its%20proof%20bundle%2C%20declaration%2C%20statement%2C%20and%20pinned%20world.%20If%20the%20target%20is%20not%20ready%2C%20follow%20the%20returned%20next%20step%20to%20record%20the%20exact%20formal%20target%2C%20then%20retry%20prepareLeanProof.%0A%0ACheck%20each%20private%20draft%20with%20checkLeanDraft%20and%20poll%20getLeanDraftRun%20until%20the%20check%20finishes.%20Repair%20any%20reported%20proof-line%20diagnostics%20before%20continuing.%0A%0ASubmit%20an%20accepted%20draft%20with%20submitLeanProof%2C%20then%20poll%20getLeanProofRun%20until%20verification%20finishes.%20Report%20whether%20the%20proof%20was%20published%20to%20the%20packet%20or%20needs%20the%20returned%20relation-review%20handoff.).

## References

1. <a id="reference-1"></a>Alexander Mednykh and Ilya Mednykh, “The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic”. arXiv:1711.00175 (2017). Mednykh and Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, equations for the even-valent circulant Laplacian and Theorem 3; exact finite-field implementation in cst101-artifact-exact-orbit-sweep https://arxiv.org/abs/1711.00175
   - Also cited at A. D. Mednykh and I. A. Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, Discrete Mathematics 342 (2019), 1772-1781
   - Also cited at Exact reconstruction in cst101-artifact-exact-orbit-sweep, independently checked at the winner by cst101-artifact-bareiss-cofactor
   - Also cited at Kirchhoff cofactor replay and Mednykh and Mednykh, Theorem 3
   - preprint; reference source; arXiv:1711.00175, checked 2026-08-01; checked 2026-07-25
   - Source use: citation_only
   - For Most spanning trees in a 10-regular circulant on 101 vertices, the reviewed source scope is Mednykh and Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, equations for the even-valent circulant Laplacian and Theorem 3; exact finite-field implementation in cst101-artifact-exact-orbit-sweep. The packet makes no inference beyond that cited scope.
   - Source named by the research packet.
2. <a id="reference-2"></a>Lonc, Parol, and Wojciechowski, Networks 30(1) (1997), 47-56; Wang and Yang 1984; Zhang, Yong, and Golin 2005; Mednykh and Mednykh 2019. Lonc, Parol, and Wojciechowski, Networks 30(1) (1997), 47-56; Wang and Yang 1984; Zhang, Yong, and Golin 2005; Mednykh and Mednykh 2019 https://dblp.org/rec/journals/networks/LoncPW97
   - Also cited at Zbigniew Lonc, Krzysztof Parol, and Jacek Wojciechowski, On the asymptotic behavior of the maximum number of spanning trees in circulant graphs, Networks 30(1) (1997), 47-56
   - website; reference source; checked 2026-07-25
   - Source use: citation_only
   - For Most spanning trees in a 10-regular circulant on 101 vertices: The literature gives exact formulas and asymptotic extremal results; the particular 42,376-orbit comparison appears to be a new finite computation.
3. <a id="reference-3"></a>Yuanping Zhang, Xuerong Yong, and Mordecai J. Golin, “Chebyshev polynomials and spanning tree formulas for circulant and related graphs,” Discrete Mathematics 298(1-3) (2005), 334-364. DOI 10.1016/j.disc.2004.10.025. Chebyshev-polynomial determinant and spanning-tree formulas for circulant and related graphs https://doi.org/10.1016/j.disc.2004.10.025
   - Also cited at Yuanping Zhang, Xuerong Yong, and Mordecai J. Golin, Chebyshev polynomials and spanning tree formulas for circulant and related graphs, Discrete Mathematics 298 (2005), 334-364
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - For Most spanning trees in a 10-regular circulant on 101 vertices, this source supplies the spanning-tree formula specialized by the finite optimizer.
4. <a id="reference-4"></a>J. F. Wang and C. S. Yang, “On the number of spanning trees of circulant graphs,” International Journal of Computer Mathematics 16(4) (1984), 229-241. DOI 10.1080/00207168408803440. classical spanning-tree formulas for circulant graphs https://doi.org/10.1080/00207168408803440
   - Also cited at J. F. Wang and C. S. Yang, On the number of spanning trees of circulant graphs, International Journal of Computer Mathematics 16 (1984), 229-241
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - For Most spanning trees in a 10-regular circulant on 101 vertices, this source supplies the classical circulant spanning-tree formula used as the packet's starting point.