An 81/29 upper bound for Tuza's conjecture
- Kind
- Theorem (an upper bound), verified in Lean 4
- Status
- Main theorems verified unconditionally in Lean 4; exact rational LP and finite-graph checks in Python; unrefereed
- Prior work
- Builds directly on Sichen Wang's 165/59 bound (arXiv:2609.13831) and extends Wang's MIT-licensed Lean 4 library; follows Haxell (1999) and Yi (2026)
The statement
In a finite simple graph , let be the maximum number of pairwise edge-disjoint triangles and the minimum number of edges meeting every triangle. Taking all edges of a maximum packing gives the trivial bound . In 1981, Zsolt Tuza conjectured that
for every finite simple graph (Erdős Problem #167), which is sharp on () and ().
Building on Haxell (1999, ), Yi (August 2026, ), and Sichen Wang (September 2026, ), this paper sharpens the universal constant in two stages:
- Theorem 1 (stage 1). Coupling helper books along sink-rooted arborescences (tightening Wang's random-bipartition private-spine term from to ) together with unmerged colored-family covers establishes , i.e. , which equals the exact optimum across every depth of the pre-elimination Lemma 2.3 linear-programming relaxation (Theorem 2).
- Theorem 3 (stage 2). Eliminating every non-private opposite edge in Wang's book cover (, where ) and combining six cover inequalities yields , i.e. , with slack , saving over Wang's and over .
Check it yourself
The universal progression on .
| Source | Universal bound | Decimal | Excess above 2 |
|---|---|---|---|
| Trivial packing edges | |||
| Haxell (1999) | |||
| Yi (August 2026) | |||
| Wang (September 2026) | |||
| Theorem 1 (stage 1) | |||
| Theorem 3 (stage 2) |
The integer combination for . Let and let denote the nonnegative decomposition parameters with , , , , and . Summing the six inequalities (cleared of denominators) with integer weights — corresponding to normalized weights — cancels every parameter except , , and , giving directly.
Concrete obstructions and benchmarks. On ( vertices, edges) , and on ( vertices, edges) . The stage-1 LP optimum is matched on an explicit -vertex, -edge colored gadget () whose three recursive covers all equal ; trying to embed it into a full graph exposes the opposite-edge exchange that yields Theorem 3.
Replay from the archive. Unpack the downloaded verification archive and run:
- Exact-arithmetic verifier (Python 3 standard library only, zero floating point):
python3 papers/tuza-triangle-cover/recompute.py - Lean 4 kernel build (Lean
v4.35.0+ Mathlib):cd lean && lake build TuzaBound && lake env lean TuzaBound/Verify.lean
Status and who checked it
- Verified unconditionally in Lean 4. The archive includes the complete Lean
v4.35.0development (28.leanfiles, 544 public declarations with 113 receipted#print axiomschecks, zerosorry, zeronative_decide, standard three axiomspropext,Classical.choice, andQuot.soundonly). It preserves character-for-character identical MathlibSimpleGraphdefinitionsnuandtaufrom Sichen Wang's MIT-licensedsichen-wang/tuza-lean(MIT license included). Theorems 1, 2(a), and 3, Lemmas 1.1 through 1.3, Corollary 3.4, and non-vacuity are checked inside the Lean 4 kernel. - Verified in exact rational Python (
recompute.py, not in Lean 4). The -vertex gadget (Theorem 2(b)), primal-dual LP certificates across all stages and residual depths through , enumeration of all unlabeled rooted trees (), canonical chain identifications (), Bell set-partition checks ( and with surviving obstructions), connected-graph census for , and benchmark graphs. - Open. Tuza's conjecture remains open. Across residual depths to , the post-elimination LP relaxation locks at .
- Unrefereed. Checked by automated proof verification and agent reviewers; no human referee has read the manuscript.
Prior work
Credited. Zsolt Tuza posed the conjecture in 1981 (surveyed in 1990). Krivelevich (1995) proved the fractional halves and . Haxell (1999) broke the trivial bound with . Yi (August 2026) improved this to and identified the barrier of Haxell's four-inequality system. Sichen Wang (September 2026, arXiv:2609.13831) broke with and released the MIT-licensed Lean 4 repository sichen-wang/tuza-lean that this work directly extends.
Searches run. Wang's 5-page preprint, all 22 upstream Lean files and MIT license of sichen-wang/tuza-lean, Yi's 4-page preprint, Erdős Problem #167, and OEIS entries A001839 and A002620 were read in full; arXiv, zbMATH Open, and GitHub were searched on 2026-11-21 for universal bounds below . On 2026-11-22, a Google Scholar sweep (5 queries) found no prior work stating this claim.
Still owed. Printed editions of Tuza (1981, 1990), Krivelevich (Discrete Math. 138, 1995, 291–295), and Haxell (Discrete Math. 195, 1999, 251–254), full texts of several 2026 restricted-class preprints, and searches on MathSciNet and Scopus.
Further reading
- Sichen Wang, "A Bound Below 2.8 for Tuza's Conjecture", arXiv:2609.13831 (2026)
- Sichen Wang,
sichen-wang/tuza-lean(MIT-licensed Lean 4 formalization, 2026) - L. Yi, "An improved upper bound for Tuza's conjecture via 2-colorable triangle families", arXiv:2608.23010 (2026)
- P. E. Haxell, "Packing and covering triangles in graphs", Discrete Mathematics 195 (1999), 251–254
- Erdős Problem #167: Tuza's conjecture