Tuza’s conjecture
In any graph, can all triangles be destroyed by deleting at most twice as many edges as the largest number of edge-disjoint triangles?
Summary
Zsolt Tuza formulated the conjecture in 1981. Deleting all three edges of each triangle in a largest packing always works, so the conjecture asks to improve the factor 3 to 2; the factor 2 would be best possible, as infinitely many graphs show.
Source
Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 18 Nov 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.