Skip to content

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

\[ n^{1/2-\varepsilon} \]

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

\[ 3n^{2-\varepsilon} \]

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

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.

Back to catalogue · Compendium introduction