Erdős Problem #134
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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 triangle-free graph has no three vertices that are pairwise adjacent. Erdős and Gyárfás asked whether every sufficiently large triangle-free graph \(G\) on \(n\) vertices with maximum degree less than
can be enlarged by adding edges only to a triangle-free graph on the same vertices with diameter two, using at most \(\delta n^2\) new edges, for any fixed positive \(\varepsilon,\delta\).
The graph must remain triangle-free. No original edges may be deleted. The degree exponent \(1/2-\varepsilon\) is crucial: allowing a large constant times \(\sqrt n\) is insufficient.
A small example
A star with at least three vertices is triangle-free and has diameter two already; no new edges are needed. An edgeless graph has infinite diameter and must acquire edges. A naive method adding every missing edge creates triangles and is invalid.
An edge between two nonadjacent vertices may be added without creating a triangle only when the endpoints have no common neighbour in the current graph. A finite checker must enforce this invariant.
What is known
PROVED. Noga Alon, Triangle-free graphs of diameter 2, establishes a stronger result: for every \(0<\varepsilon<1/6\) and sufficiently large \(n\), any triangle-free graph with maximum degree at most \(n^{1/2-\varepsilon}\) can be extended, while remaining triangle-free, to diameter two by adding fewer than
edges. Since \(3n^{-\varepsilon}\to0\), this is below \(\delta n^2\) for all sufficiently large \(n\) and any fixed \(\delta>0\).
For an original parameter \(\varepsilon\ge1/6\), choose a smaller positive exponent below \(1/6\); the original degree assumption then implies the weaker one, and the extra-edge count remains \(o(n^2)\). Erdős and Gyárfás previously proved a case with maximum degree of order \(\log n/\log\log n\). The author's exact primary result was checked at theorem-summary level, not fully reproved.
GCL's current state
The pinned and maintained Erdős #134 classify it PROVED and report an external Lean formalization. Original source issue: #1403. The external Lean proof has not been replayed or admitted into GCL's protected formal stack.
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 proof task is to derive the conclusion for fixed positive \(\delta\) from Alon's \(3n^{2-\varepsilon}\) estimate with fully explicit quantifiers and the large-exponent reduction. A second finite fixture should verify that an edge-addition candidate preserves original edges, has no triangle, and has diameter exactly two. Acceptance: the asymptotic arithmetic is checked independently and finite checks do not masquerade as a new construction theorem.
Sources and claim boundaries
- Alon, author-hosted original paper, quantitative extension theorem.
- Erdős #134, historical notes; GCL issue #1403.
No new extension theorem, independent protected Lean certification, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1403 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.