Tuza's conjecture

Tuza's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning triangles in undirected graphs.

is the "triangle packing number", the largest number of edge-disjoint triangles that it is possible to find in

[1] It can be computed in polynomial time as a special case of the matroid parity problem.

is the size of the smallest "triangle-hitting set", a set of edges that touches at least one edge from each triangle.

, any triangle-hitting set must include at least one edge from each triangle of the optimal packing, and none of these edges can be shared between two or more of these triangles because the triangles are disjoint.

, one can construct a triangle-hitting set of size

by choosing all edges of the triangles of an optimal packing.

, even the ones not in the packing, because otherwise the packing could be made larger by adding any unhit triangle.

[1] Tuza's conjecture asserts that the second inequality is not tight, and can be replaced by

That is, according to this unproven conjecture, every undirected graph

has a triangle-hitting set whose size is at most twice the number of triangles in an optimal packing.

[1][3] If true, it would be best possible: there are infinitely many graphs for which

, including all of the block graphs whose blocks are cliques of 2, 4, or 5 vertices.

[1] The conjecture is known to hold for planar graphs,[1] and more generally for sparse graphs of degeneracy at most six.

[4] (Planar graphs have degeneracy at most five.)

[1] For random graphs in the Erdős–Rényi–Gilbert model, it is true with high probability.

[7] Although Tuza's conjecture remains unproven, the bound

Packing and covering triangles in the complete graph . The maximum number of edge-disjoint triangles in this graph is two (left). If four edges are removed from the graph (red edges, right), the remaining subgraph becomes triangle-free , and more strongly bipartite (as shown by the blue and yellow vertex coloring). According to Tuza's conjecture, in any graph, it is possible to remove twice as many edges as the maximum triangle packing size, and eliminate all triangles. is an extreme case, for which exactly twice the packing size is needed.