Tuza's conjecture 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.
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.
