Erdős Problem #136
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (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
Colour the edges of the complete graph \(K_n\). Require every set of four vertices to use at least five distinct edge colours among its six edges. If \(f(n)\) is the fewest colours that can be used globally, how does it grow as \(n\) increases? The requirement is local to each four-vertex complete graph, but colours are shared throughout the entire host graph.
A small example
For \(n=4\), the entire graph has six edges and the rule requires five distinct colours; using five is possible, so \(f(4)=5\). For \(n=3\), there is no four-vertex subset, and the condition is vacuous. Small sizes must not be substituted into asymptotic inequalities stated for sufficiently large \(n\).
What is known
SOLVED as an asymptotic problem. Erdős and Gyárfás obtained bounds with leading terms \(5n/6\) and \(n\). Bennett, Cushman, Dudek and Prałat established \(f(n)\sim 5n/6\) in 2022; Joos and Mubayi found a shorter proof. The exact value for every \(n\) is not part of the asserted asymptotic result. The maintained Erdős #136 records these names and the older example \(f(9)=8\). The full original proofs have not been independently replayed in this source audit.
GCL's current state
Pinned catalogue status SOLVED, original GCL source issue #1405. The original problem-to-issue mapping is fixed; there is no protected Formal Conjectures statement for this problem in the admitted 85f86371 revision. The asymptotic constant is an attributed published result, not a new GCL theorem.
The original source assignment has an authenticated RESULT/1 report. This is unadjudicated source evidence, not a proof certificate or accepted article.
What remains
Build an exhaustive edge-colouring checker for \(K_4,K_5\), canonicalizing colours by their order of first use. Acceptance: verify \(f(4)=5\), count distinct colours globally, and reject any four-clique using four or fewer. The bounded fixture cannot prove the asymptotic result.
Sources and claim boundaries
- Maintained Erdős problem #136, with primary Bennett–Cushman–Dudek–Prałat and Joos–Mubayi references.
- Original GCL issue #1405; frozen catalogue teorth/erdosproblems@536408716724a2402bdfa7c1d764bf83d64a8c89.
No full source-proof rederivation, formal certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1405 — 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.