Erdős Problem #167
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: falsifiable (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
In a graph \(G\), let \(\nu_\triangle(G)\) be the maximum number of edge-disjoint triangles, and let \(\tau_\triangle(G)\) be the minimum number of edges whose deletion destroys every triangle. Tuza's conjecture asks whether
for every finite graph. The edge-disjoint triangles may share vertices but not edges. A triangle-hitting set must meet every triangle, whether or not it belongs to a particular chosen packing.
A small example
In \(K_4\), every two distinct triangles share an edge. Therefore at most one triangle can be chosen edge-disjointly, so \(\nu_\triangle(K_4)=1\). Removing two opposite edges destroys all four triangles, and deleting only one does not, so \(\tau_\triangle(K_4)=2\). The proposed factor two is sharp.
The immediate trivial upper bound is three: choose a maximal edge-disjoint packing of \(k\) triangles, then remove all three edges from each chosen triangle. Any remaining triangle would be edge-disjoint from the packing and contradict maximality. Thus \(\tau_\triangle(G)\le3\nu_\triangle(G)\); improving three to two is the genuine challenge.
What is known
OPEN and FINITELY FALSIFIABLE. Tuza's conjecture is recorded in Erdős #167, with \(K_4\) and \(K_5\) demonstrating optimality of the factor two. Haxell (1999) proved the improved asymptotic bound
in the applicable asymptotic setting. Kahn and Park (2022) established the conjectured inequality for random graphs in their model; random-graph validity does not imply the universal theorem.
There are also related fractional versions, but fractional triangle packings or hitting weights are not integer edge-disjoint packings or integer edge deletions. Substituting one for another changes the conjecture.
GCL's current state
The pinned status is FALSIFIABLE, meaning a single finite counterexample would refute it. The maintained source, edited October 2025, still calls it open. Original source issue: #1436. No purported finite counterexample or independently verified full proof is claimed. Exact edge semantics and both optimization directions are the material source-fidelity requirements.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded task enumerates simple graphs on at most six vertices, lists every triangle, computes maximum pairwise edge-disjoint triangle families and minimum edge hitting sets using integer brute force, and checks \(\tau_\triangle\le2\nu_\triangle\). Acceptance: \(K_4\) produces \((\nu,\tau)=(1,2)\) and each candidate optimization is verified independently by exhaustive search. Stop after a finite certificate; observing no small counterexample cannot prove Tuza's conjecture.
Sources and claim boundaries
- Erdős #167, source for Tuza's conjecture, Haxell and Kahn–Park partial results.
- Original GCL issue #1436.
No universal proof, new counterexample, formal certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1436 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.