Papex

Open problem · Mathematics · since 1981 · Open

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.

More in Mathematics