Tuza's Triangle Packing–Covering Conjecture

For a finite simple graph $G$, write $\nu_3(G)$ for the maximum number of pairwise edge-disjoint triangles and $\tau_3(G)$ for the minimum number of edges meeting every triangle. Removing the three edges of each triangle in a maximum packing destroys all triangles, so $\tau_3(G)\le 3\nu_3(G)$ trivially, while any cover must use at least one edge from each packed triangle, giving $\tau_3(G)\ge\nu_3(G)$. Tuza conjectured in 1981 that the true worst-case ratio is $2$: every graph satisfies $\tau_3(G)\le 2\nu_3(G)$ [Tuza1981Triangles]. The factor $2$ would be sharp, as small complete graphs show.

Haxell proved a general bound with a constant strictly below the trivial factor $3$ [Haxell1999Tuza], and by now the fractional relaxation of the problem, asymptotic versions, and many special graph classes are well understood. Recent work continues to extend the verified territory, for instance to random geometric graphs, where almost-perfect triangle packings are constructed [BennettEtAl2026Tuza].

Despite this progress the constant $2$ has not been established in full generality, and the conjecture remains open: a proof must handle arbitrary graphs, not only the structured or random classes treated so far.