HEXAGONbeta

All τk\tau_k-maximal graphs have the same size

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Deep Bhattacharjee ↗

Version 1 / Oct 22, 2026 / CC BY 4.0

Abstract

A graph is τk\tau_k-maximal if none of its subgraphs has k+1k+1 edge-disjoint spanning trees, but adding any missing edge creates such a subgraph. Wang and Tian conjectured that every τk\tau_k-maximal graph on n≥2k+2n\ge 2k+2 vertices has exactly (k+1)(n−1)−1(k+1)(n-1)-1 edges. We prove this conjecture.

Provenance statement

Deep Bhattacharjee chose the problem and directed the work. Claude (Anthropic), through Claude Code, carried out the searches and computations, wrote the checking programs and the Lean 4 proofs and drafted the paper. Settles the Wang–Tian conjecture. The proofs are written out in the paper; the programs and their outputs are in the release. The author approved the final version. Code and data: release v1.0.0, https://github.com/creelie/eConjectureTauMaximal/releases/tag/v1.0.0.
AI provenance filesAI-PROVENANCE-HEXAGON.md · 1 KB

Tools used

Anthropic
Claude CodeVersion Opus 5.5 Ultracode

References

  1. J. Edmonds, Submodular functions, matroids, and certain polyhedra , in: Combinatorial Structures and their Applications (Calgary, 1969), Gordon and Breach, New York, 1970, pp. 69--87. Reprinted in: Combinatorial Optimization---Eureka, You Shrink!, Lecture Notes in Comput. Sci. 2570 , Springer, Berlin, 2003, pp. 11--26. 10.1007/3-540-36478-1_2DOI
  2. G. Laman, On graphs and rigidity of plane skeletal structures , J. Engrg. Math. 4 (1970), 331--340. 10.1007/BF01534980DOI
  3. A. Lee and I. Streinu, Pebble game algorithms and sparse graphs , Discrete Math. 308 (2008), 1425--1437. 10.1016/j.disc.2007.07.104DOI
  4. C. St. J. A. Nash-Williams, Edge-disjoint spanning trees of finite graphs , J. London Math. Soc. 36 (1961), 445--450. 10.1112/jlms/s1-36.1.445DOI
  5. W. T. Tutte, On the problem of decomposing a graph into nn connected factors , J. London Math. Soc. 36 (1961), 221--230. 10.1112/jlms/s1-36.1.221DOI
  6. Q. Wang and Y. Tian, Extremal graphs with no subgraph admitting k+1k+1 edge-disjoint spanning trees , preprint, 2026. arXiv:2606.28198 (https://arxiv.org/abs/2606.28198)arXiv
  7. W. Whiteley, Some matroids from discrete applied geometry , in: Matroid Theory (Seattle, 1995), Contemp. Math. 197 , Amer. Math. Soc., Providence, RI, 1996, pp. 171--311. 10.1090/conm/197/02540DOI

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositCurrentOct 22, 2026