Proved theorem Lean Unrefereed

An 81/29 upper bound for Tuza's conjecture

Edition 2 · On this site since · last revised · Verify & co-author
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)
On this page
  1. The statement
  2. Check it yourself
  3. Status and who checked it
  4. Prior work
  5. Further reading

The statement

In a finite simple graph G=(V,E)G = (V,\allowbreak E), let ν(G)\nu(G) be the maximum number of pairwise edge-disjoint triangles and τ(G)\tau(G) the minimum number of edges meeting every triangle. Taking all edges of a maximum packing gives the trivial bound τ(G)≤3ν(G)\tau(G) \le 3\nu(G). In 1981, Zsolt Tuza conjectured that

τ(G)≤2ν(G)\tau(G) \le 2\nu(G)

for every finite simple graph (Erdős Problem #167), which is sharp on K4K_4 (ν=1,τ=2\nu = 1,\allowbreak \tau = 2) and K5K_5 (ν=2,τ=4\nu = 2,\allowbreak \tau = 4).

Building on Haxell (1999, 6623ν(G)\frac{66}{23}\nu(G)), Yi (August 2026, 6322ν(G)\frac{63}{22}\nu(G)), and Sichen Wang (September 2026, 16559ν(G)≈2.796610 ν(G)\frac{165}{59}\nu(G) \approx 2.796610\,\nu(G)), 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 +38h+\frac{3}{8}h to +14h^≤+14h+\frac{1}{4}\hat{h} \le +\frac{1}{4}h) together with unmerged colored-family covers establishes 250 τ(G)≤699 ν(G)250\,\tau(G) \le 699\,\nu(G), i.e. τ(G)≤699250ν(G)=2.796 ν(G)\tau(G) \le \frac{699}{250}\nu(G) = 2.796\,\nu(G), which equals the exact optimum across every depth K≥1K \ge 1 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 (τ(G)+2c≤3n+h^+2h0\tau(G) + 2c \le 3n + \hat{h} + 2h_0, where h=h^+h0h = \hat{h} + h_0) and combining six cover inequalities yields 29 τ(G)≤81 ν(G)29\,\tau(G) \le 81\,\nu(G), i.e. τ(G)≤8129ν(G)≈2.793103 ν(G)\tau(G) \le \frac{81}{29}\nu(G) \approx 2.793103\,\nu(G), with slack 29 τ(G)+2h1≤81 ν(G)29\,\tau(G) + 2h_1 \le 81\,\nu(G), saving 61711ν(G)\frac{6}{1711}\nu(G) over Wang's 16559ν(G)\frac{165}{59}\nu(G) and 217250ν(G)\frac{21}{7250}\nu(G) over 699250ν(G)\frac{699}{250}\nu(G).

Check it yourself

The universal progression on [2,3][2,\allowbreak 3].

Source Universal bound Decimal Excess above 2
Trivial packing edges 33 3.0000003.000000 1.0000001.000000
Haxell (1999) 66/2366/23 2.8695652.869565 0.8695650.869565
Yi (August 2026) 63/2263/22 2.8636362.863636 0.8636360.863636
Wang (September 2026) 165/59165/59 2.7966102.796610 0.7966100.796610
Theorem 1 (stage 1) 699/250699/250 2.7960002.796000 0.7960000.796000
Theorem 3 (stage 2) 81/2981/29 2.7931032.793103 0.7931030.793103

The integer combination for 81/2981/29. Let n=ν(G)n = \nu(G) and let (a,m,b,c,d,h^,h0,h1)(a,\allowbreak m,\allowbreak b,\allowbreak c,\allowbreak d,\allowbreak \hat{h},\allowbreak h_0,\allowbreak h_1) denote the nonnegative decomposition parameters with a+m≤na + m \le n, b≤mb \le m, c+d≤bc + d \le b, h^+h0=h≤b\hat{h} + h_0 = h \le b, and h1≤ch_1 \le c. Summing the six inequalities (cleared of denominators) with integer weights (10,1,8,1,2,4)(10,\allowbreak 1,\allowbreak 8,\allowbreak 1,\allowbreak 2,\allowbreak 4) — corresponding to normalized weights (10,4,8,1,2,4)(10,\allowbreak 4,\allowbreak 8,\allowbreak 1,\allowbreak 2,\allowbreak 4) — cancels every parameter except nn, τ\tau, and +2h1≥0+2h_1 \ge 0, giving 29 τ(G)+2h1≤81 ν(G)29\,\tau(G) + 2h_1 \le 81\,\nu(G) directly.

Concrete obstructions and benchmarks. On K4K_4 (44 vertices, 66 edges) ν=1,τ=2\nu = 1,\allowbreak \tau = 2, and on K5K_5 (55 vertices, 1010 edges) ν=2,τ=4\nu = 2,\allowbreak \tau = 4. The stage-1 LP optimum 699/250699/250 is matched on an explicit 3232-vertex, 6262-edge colored gadget H14,3,1H_{14,3,1} (ν=τ∗=τ=14\nu = \tau^* = \tau = 14) whose three recursive covers all equal 3636; 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
Universal bounds on [2,3][2,\allowbreak 3] from 33 down to 81/2981/29, the intermediate LP ablation ladder showing why helper-arborescence coupling and unmerged colored covers must act together to pass 165/59165/59, and exact LP invariance across residual depths K=1K = 1 to 1212.Full size

Status and who checked it

  • Verified unconditionally in Lean 4. The archive includes the complete Lean v4.35.0 development (28 .lean files, 544 public declarations with 113 receipted #print axioms checks, zero sorry, zero native_decide, standard three axioms propext, Classical.choice, and Quot.sound only). It preserves character-for-character identical Mathlib SimpleGraph definitions nu and tau from Sichen Wang's MIT-licensed sichen-wang/tuza-lean (MIT license included). Theorems 1, 2(a), and 3, Lemmas 1.1 through 1.3, Corollary 3.4, and K4K_4 non-vacuity are checked inside the Lean 4 kernel.
  • Verified in exact rational Python (recompute.py, not in Lean 4). The 3232-vertex gadget H14,3,1H_{14,3,1} (Theorem 2(b)), primal-dual LP certificates across all stages and residual depths K=1K = 1 through 1212, enumeration of all 8585 unlabeled rooted trees (s≤7s \le 7), 9292 canonical chain identifications (r≤4r \le 4), Bell set-partition checks (B10=115,975B_{10} = 115,\allowbreak 975 and B9=21,147B_9 = 21,\allowbreak 147 with 00 surviving obstructions), connected-graph census for ∣V∣≤6|V| \le 6, and 1313 benchmark graphs.
  • Open. Tuza's conjecture τ(G)≤2ν(G)\tau(G) \le 2\nu(G) remains open. Across residual depths K=1K = 1 to 1212, the post-elimination LP relaxation locks at 8129\frac{81}{29}.
  • 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 τ(G)≤2ν∗(G)\tau(G) \le 2\nu^*(G) and ν∗(G)≤2ν(G)\nu^*(G) \le 2\nu(G). Haxell (1999) broke the trivial bound 33 with 6623ν(G)\frac{66}{23}\nu(G). Yi (August 2026) improved this to 6322ν(G)\frac{63}{22}\nu(G) and identified the 5419ν(G)\frac{54}{19}\nu(G) barrier of Haxell's four-inequality system. Sichen Wang (September 2026, arXiv:2609.13831) broke 2.82.8 with 16559ν(G)\frac{165}{59}\nu(G) 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 165/59165/59. 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