Tuza’s triangle packing conjecture

Find as many triangles as possible in a finite simple undirected graph without reusing an edge; sharing dots is allowed. Then remove edges to destroy every triangle. On four dots all joined to one another, any two triangles share an edge, so only one can be packed. Removing two opposite links destroys all four triangles. Can every graph be cleared using at most twice its largest packing size?[1] [2]

How tightly can independent triangle obstructions predict the number of edges needed to remove them all? In $K_4$, the graph joining every pair of four vertices, every pair of triangles shares an edge. Thus the maximum edge-disjoint triangle packing has size one. No single edge hits all four triangles, but two opposite edges do, so the minimum triangle edge cover has size two.

For any finite simple undirected graph $G$, let $\nu_{\triangle}(G)$ count a largest edge-disjoint triangle packing and $\tau_{\triangle}(G)$ count a smallest edge set meeting every triangle. Vertices may be shared by packed triangles. Is $\tau_{\triangle}(G)\leq2\nu_{\triangle}(G)$ always true? The example shows that a universal factor smaller than two is impossible.[1] [2]

Removing all three edges of each triangle in a largest packing always works. The target is to reduce that general factor from three to two. The 2026 preprints report a maximum-degree-seven case and a general factor still above two; their proofs and computational certificates are not independently checked here.[1] [2]

The August maximum-degree-seven claim is restricted. September’s reported 165/59 coefficient does not reach the conjectured 2.[1] [2]

Many overlapping triangles can disappear when one shared edge is removed, so simply counting all triangles exaggerates the required work. Edge-disjoint triangles instead force separate removals. Relating these two measures tells us how unavoidable local obstructions constrain one operation that clears the whole graph.[1] [2]

The elementary factor three comes from deleting every edge in a maximum packing: any surviving triangle could otherwise enlarge that packing. Reaching factor two requires using how triangles outside the packing overlap its edges, rather than paying for all three edges independently. This connects a certificate of necessary deletions to a collective deletion strategy. It is the special incidence structure of triangles in a graph, not a count of triangles alone, that could narrow the gap.[1] [2]