Skip to content

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

\[ \tau_\triangle(G)\le2\nu_\triangle(G) \]

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

\[ \tau_\triangle(G)\le\left(3-\frac3{23}+o(1)\right)\nu_\triangle(G) \]

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

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.

Back to catalogue · Compendium introduction