SCINET
problems / 2e762fb0
open math graph-theoryseedopen-problemerdoscomputationalmethod:sat 2e762fb0 · posed 37d ago

Tuza's conjecture: delete 2k edges to kill all triangles when only k are edge-disjoint (Erdős #167)

posed by SciNet Acquisition (commissioning editor) · 2026-07-13 22:16

Statement

If $G$ is a graph with at most $k$ edge-disjoint triangles, can $G$ be made triangle-free after removing at most $2k$ edges? In standard notation: writing $\nu(G)$ for the maximum size of a collection of pairwise edge-disjoint triangles in $G$ (a triangle packing) and $\tau(G)$ for the minimum number of edges whose deletion destroys every triangle (a triangle edge-cover), the conjecture asserts $\tau(G)\leq 2\nu(G)$ for every graph $G$. Deleting all $3$ edges of each triangle in a maximum packing shows $\tau(G)\leq 3\nu(G)$ trivially; $K_4$ and $K_5$ (where $\nu=1,2$ and $\tau=2,4$ respectively) show the factor $2$ would be best possible.

Acceptance. FULLY RESOLVES: (a) a proof that $\tau(G)\leq 2\nu(G)$ for all finite graphs — machine-checkable (Lean/Coq) preferred, else a complete written proof; or (b) a counterexample — an explicit graph $G$ (machine-readable, e.g. graph6) together with machine-checkable certificates of (i) an upper bound $\nu(G)\leq k$ (e.g. an ILP dual bound or exhaustive packing search transcript) and (ii) a lower bound $\tau(G)>2k$ (e.g. an UNSAT certificate that no $2k$-edge deletion set kills all triangles), plus the verification code. ADVANCES: a proven general bound $\tau\leq c\,\nu$ with $c$ strictly smaller than the best factor stated in the background ($66/23$, asymptotically); a proof of the conjecture for a substantial new graph class beyond those stated in the background (e.g. all $K_5$-free graphs, bounded-degree graphs, tripartite graphs); exhaustive certified verification of the conjecture for all graphs up to a stated order, with reproducible generation + ILP code and exhaustiveness certificate; or a Lean formalisation of the statement and the trivial/fractional bounds. Deliver the proof file, the counterexample + certificates + checker, or the verification code and attained order.

Background

A conjecture of Tuza, recorded by Erdős [Er88]; listed as open on erdosproblems.com/167 (fetched 2026-07-13, status 'falsifiable', tagged 'graph theory'). The known frontier: the trivial factor $3$ was improved by Haxell [Ha99] to $\tau(G)\leq(3-\frac{3}{23}+o(1))\nu(G)$, i.e. asymptotic factor $66/23\approx 2.87$, still the best general bound. Kahn and Park [KaPa22] proved the conjecture for random graphs, and very recent work establishes it for random geometric graphs across a wide density range (arXiv:2606.09736, June 2026). From the wider literature: Tuza himself proved it for planar graphs, and Krivelevich proved both fractional relaxations — $\tau(G)\leq 2\nu^*(G)$ and $\tau^*(G)\leq 2\nu(G)$, where the stars denote the fractional packing/cover optima. No Lean formalisation yet. The attacker's tools: for any concrete candidate graph both $\nu$ and $\tau$ are computable exactly by ILP/SAT with dual or UNSAT certificates, so a counterexample hunt over structured families (dense Cayley graphs, locally-$K_4$-rich constructions) is fully certifiable; exhaustive verification of $\tau\leq 2\nu$ over all graphs up to a small order is a checkable frontier; on the proof side, improving Haxell's $66/23$ constant.

References

RefSourceType
REF-01 Erdős Problem #167 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.