Problem 167

If $G$ is a graph with at most $k$ edge disjoint triangles then can $G$ be made triangle-free after removing at most $2k$ edges?

Source: erdosproblems.com/167

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Falsifiable, the site's label (FALSIFIABLE): the problem is open and a single finite counterexample would disprove it. The label is a note on an open problem, not a claim; no proof claim on the statement for every graph is recorded on the site or found elsewhere. No proof, disproof or proof claim for the statement was found in the search whose scope the Current assessment records. The best refereed general bound is Haxell's $\tau(G)\le\frac{66}{23}\nu(G)$ (Discrete Math. 1999, Theorem 5, its four-lemma proof followed); two preprints of August and September 2026 claim $\frac{63}{22}$ and $\frac{165}{59}\approx2.797$ , unreviewed, and as constants above $2$ they settle no instance, so they have no claim pages. The conjecture holds for the binomial random graph at every density with high probability (Kahn and Park, Theorem 1.2, refereed) and for several classes attested second-hand (planar graphs, $K_4$ -free planar graphs with constant $\frac32$ , small treewidth, threshold graphs, dense graphs). The refereed results of Chahua and Gutiérrez are an accepted partial claim on its claim page; they do not decide the question for every graph, so the standing stays open. The classes attested second-hand have no claim pages until each statement is checked in its paper or a review. This is a bounded negative finding, not a certificate of openness.

Er88: Erdős, P., Problems and results in combinatorial analysis and graph theory. Discrete Math. 72 (1988), 81--92; Section 10, printed p. 90. Library home: Erdős 1988; paged at Erdős 1988, Problem (p. 90, Section 10).
Tu81: Tuza, Zs., Conjecture. Finite and Infinite Sets (Eger, 1981), Colloq. Math. Soc. János Bolyai 37, North-Holland (1984), p. 888, as [KaPa22]'s reference [16] cites it. Not held; the Chahua--Gutiérrez abstract dates the conjecture to 1982 and its introduction to 1981.
Ha99: Haxell, P. E., Packing and covering triangles in graphs. Discrete Math. 195 (1999), no. 1--3, 251--254, doi:10.1016/S0012-365X(98)00183-6 (per its Crossref record). Theorem 5, printed p. 254 (PDF p. 4 of the publisher's open-archive file): $\tau(G)\le(3-\varepsilon)\nu$ with $\varepsilon\ge3/23$ , that is $\tau(G)\le\frac{66}{23}\nu(G)$ ; the definitions, the trivial bounds and Tuza's conjecture with its Bolyai citation, p. 251 (PDF p. 1); Lemmas 1--4 and their proofs, pp. 252--254 (PDF pp. 2--4); the closing remark on $(23-\sqrt{481})/8$ , p. 254. Its bound is also quoted by [KaPa22], p. 1, [Yi26], p. 1, and [ChGu25], p. 1. Library home: Haxell 1999; paged at Haxell 1999, Theorem 5.
KaPa22: Kahn, J. and Park, J., Tuza's conjecture for random graphs. Random Structures Algorithms 61 (2022), no. 2, 235--249, doi:10.1002/rsa.21057 (published online 13 November 2021). Cited from arXiv:2007.04351v2 (10 July 2020, 13 pp.); Conjecture 1.1 and Theorem 1.2, p. 1; the reference list, p. 12; the journal text was not compared. Library home: Kahn and Park 2022; paged at Kahn and Park 2022, Theorem 1.2 (p. 1).
Yi26: Yi, L., An improved upper bound for Tuza's conjecture via 2-colorable triangle families. arXiv:2608.23010v1 (24 August 2026), 4 pp.; a preprint; Theorem 1, p. 1; Corollary 1, p. 3; the closing remarks and the "Disclosure of AI use", p. 4. Library home: Yi 2026; paged at Yi 2026, Theorem 1 (p. 1) and Yi 2026, Corollary 1 (p. 3).
Wa26: Wang, S., A bound below 2.8 for Tuza's conjecture. arXiv:2609.13831v1 (12 September 2026), 5 pp.; a preprint cited from its arXiv record (abstract and comment); the paper is not held.
ChGu25: Chahua, L. and Gutiérrez, J., On Tuza's conjecture in dense graphs. Discrete Appl. Math. 377 (2025), 225--233, doi:10.1016/j.dam.2025.06.049 (per its Crossref record). Cited from arXiv:2405.11409v1 (18 May 2024, 12 pp.; accessed): the abstract and introduction, pp. 1--2; Theorem 5, p. 3; Theorem 12, p. 6; Corollary 13 and Theorem 15, p. 7; the journal text was not compared. Library home: Chahua and Gutiérrez 2025; paged at Chahua and Gutiérrez 2025, Theorem 5 (p. 3), Chahua and Gutiérrez 2025, Corollary 13 (p. 7) and Chahua and Gutiérrez 2025, Theorem 15 (p. 7).

Problem 167

Status

Proof claims

Discussion