Skip to content

Erdős Problem #834

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: graph theory, hypergraphs.

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

The word critical has two different mathematical meanings, one about hitting all hyperedges with a small set and another about losing chromatic number upon an edge deletion. The minimum-degree-seven question has opposite answers under these definitions.

The term 3-critical 3-uniform hypergraph has two non-equivalent meanings. Transversal-critical: minimum edge-hitting set has size 3 and drops to at most 2 after deleting any edge. Chromatic-critical: chromatic number 3, dropping to <=2 after removing any edge or vertex. The minimum degree >=7 example is IMPOSSIBLE for transversal-critical, but EXISTS for chromatic-critical.

A small example

Complete 3-uniform K5 has ten triples, chromatic number 3 (2-coloring five vertices forces a monochromatic three-set); after deleting any edge, choose precisely that triple as one color class and remaining two vertices as other, so the remaining graph is 2-colorable. Deleting any vertex produces K4^3, also 2-colorable. Every original vertex lies in six triples, not seven. This tests chromatic-critical definition but is NOT Li's nine-vertex witness.

This finite calculation is not an asymptotic or all-parameter proof.

What is known

Maintained /latex/834 read 2026-10-14. R. Li (2025), original arXiv manuscript On an Erdős-Lovász problem: 3-critical 3-graphs of minimum degree 7 proves transversal critical 3-graphs contain a vertex of degree <=6, and gives a chromatic-critical 3-uniform hypergraph on nine vertices with minimum degree 7. Registry SOLVED is ambiguous unless paired with definition. The author's public abstract confirms both formal interpretations; the full nine-vertex incidence list and its edge-deletion certificate have not been independently reconstructed here. An externally reported proof should not be mistaken for a GCL theorem certificate.

The complete three-uniform hypergraph on five vertices is chromatic three-critical. Five vertices in two colors force a monochromatic triple; deleting any edge permits two-coloring by putting the three vertices of that edge in one class and the other two in the other class. Deleting a vertex leaves a two-colorable four-vertex complete three-graph. Its degree is only six. Li's nine-vertex degree-seven example is different and must be separately replayed. Under transversal criticality Li instead rules out minimum degree seven.

GCL's current state

The authenticated source return has disposition STATUS_CONFLICT. This is an editorially reviewed explanatory article under protected batch EC-BULK-005-R5; its original STATUS_CONFLICT source remains preserved. Published results remain attributed to their authors; original source conflicts and independent full-proof-review limits are not silently cleared by publishing the manuscript.

What remains

Implement exact hypergraph two-colorability under edge/vertex deletion for K5^3 and transversal minimum; independently replay Li 2025 9-vertex 7-regular example, and never publish answer without defining 3-critical.

The original primary mathematical proofs, quantified status, finite definitions and deployed rendering must be independently checked before protected admission. No such admission is claimed here.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2105 — 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