Tuza's conjecture (Tuza 1990) asserts that the minimum number 
of edges meeting every
triangle of a simple graph 
is at most twice the maximum number 
of pairwise edge-disjoint triangles:
 |
Here a triangle is a copy of the cycle graph 
. The complete graph 
attains equality, with 
and 
. The conjecture is problem 167 in the Erdős
problems collection.
The distinction between edge-disjoint and vertex-disjoint triangles can be arbitrarily large. For 
, add a graph
vertex 
adjacent to every graph vertex of the complete
bipartite graph 
to form 
. Every graph triangle
contains 
, while a perfect matching
of 
extends to 
edge-disjoint triangles. The 
edges from 
to either part meet every graph
triangle, so 
(Lu 2026).
Kandasamy (2026) proved the conjecture for every simple graph of maximum vertex degree at most 10. This does not settle the general conjecture. Kandasamy (2026) reports that AI wrote the verification code and assisted with part of a proof lemma. The remaining mathematics was developed without AI assistance.
Zeng (2026) reported the inequality for a split graph whose vertex set has a specified set
partition 
, where 
is an eight-vertex clique and 
is an independent
vertex set. Among the vertices of 
with at least two neighbors in 
, at most two distinct neighborhoods
in 
are allowed, each with arbitrary multiplicity. The argument reduces this infinite
class to 44,702 cases, with an explicit triangle cover and an explicit packing of
edge-disjoint triangles for each case. A standalone program checks these certificates
using exact arithmetic. Codex assisted with proof strategies, verification programs,
and certificate construction. As of Oct. 27, 2026, the manuscript had not undergone
peer review. The result does not settle the conjecture for all split
graphs.
MathIsEvenEasier (2026) reported the inequality for every finite simple graph with a set
partition 
into a clique and an independent
vertex set, provided the vertices of 
with at least two neighbors in 
have at most two distinct neighborhoods
in 
. The number of vertices
in 
, the overlap of the two neighborhoods,
and their multiplicities are unrestricted. Thus the result extends Zeng's (2026)
eight-vertex case. The author credits Codex running GPT-6 Astra with the proof
development, certificates, and Lean formalization. The project reports a successful
source build checking the graph reductions and certificate
computations. As of Nov. 3, 2026, independent specialist auditing of the complete
statement and proof had not been reported.
