Skip to content

Erdős Problem #151

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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

A maximal clique is a set of pairwise adjacent vertices that cannot be enlarged by adding another vertex. A clique transversal is a set of vertices meeting every maximal clique that has at least two vertices. Let \(\tau(G)\) be the smallest such transversal size.

For each \(n\), let \(H(n)\) be the largest integer such that every triangle-free graph on \(n\) vertices has an independent set of at least \(H(n)\) vertices. Erdős and Gallai ask whether, for every graph \(G\) on \(n\) vertices,

\[ \tau(G)\le n-H(n). \]

The cliques to hit are maximal, not all cliques, and isolated vertices do not require coverage.

A small example

In a triangle-free graph, every edge forms a maximal clique of size two. A clique transversal is then a vertex cover, whose minimum size equals \(n-\alpha(G)\), where \(\alpha(G)\) is the independence number. By definition \(\alpha(G)\ge H(n)\), so the conjecture is automatically true when \(G\) is triangle-free.

For the complete graph \(K_n\), only the whole vertex set is maximal, and one vertex hits it; thus \(\tau(K_n)=1\). Neither this trivial dense case nor the triangle-free case settles the question for general graphs with overlapping large maximal cliques.

What is known

The universal inequality remains OPEN. The maintained Erdős #151, edited December 2025, credits Erdős and Gallai with the original question and notes that they could not resolve it even for \(K_4\) free graphs. A general but weaker estimate \(\tau(G)\le n-\sqrt n\) is recorded. The extremal function \(H(n)\) is governed by independence bounds for triangle-free graphs; replacing it with a guessed asymptotic would introduce an unjustified step.

The maintained page contains a proof claim in discussion, but does not classify the conjecture as proved. Without a verified primary argument or an admitted formal proof, the claim is not a mathematical status change. A nonmaximal triangle nested inside a four-clique is not a separate clique that the transversal must hit: overlooking maximality changes the set-cover problem.

GCL's current state

The pinned catalogue and maintained page classify #151 as OPEN. Original source issue: #1420. The elementary triangle-free reduction is independently proved above; the all-graph statement and external proof claim remain unadjudicated. No independent exact theorem or Lean certification is claimed.

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 graphs on up to six vertices, lists inclusion-maximal cliques of size at least two, computes their minimum transversal size, and separately computes \(H(n)\) by exhaustive enumeration of triangle-free graphs. Acceptance: isolated vertices create no clique constraints, the triangle-free identity \(\tau(G)=n-\alpha(G)\) holds, and the conjectured inequality is checked only over enumerated finite cases. Failing to find a small counterexample would not establish the theorem.

Sources and claim boundaries

No proof of the general clique-transversal conjecture, independently reviewed discussion claim or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1420 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • 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