Skip to content

Erdős problem 619

Erdős Problem 619 [EGR98, Er99]: For a triangle-free graph GG let hr(G)h_r(G) be the smallest number of edges that need to be added to GG so that it has diameter rr (while preserving the property of being triangle-free). Is it true that there exists a constant c>0c>0 such that if GG is a connected graph on nn vertices then h4(G)<(1−c)nh_4(G)<(1-c)n?

No current result

No reviewed Result is current in Vela Mathematics Program. Retained source material is shown below.

Retained declaration

FormalConjectures/ErdosProblems/619.lean

Formal Conjectures

FormalConjectures/ErdosProblems/619.leanErdos619.erdos_6194 linesExact file
False ↔  ∃ c > 0,    ∀ (V : Type) [inst : Fintype V] (G : SimpleGraph V),      G.Connected → G.CliqueFree 3 → ↑(Erdos619.minNewEdges 4 G) < (1 - c) * ↑(Fintype.card V)
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Proof manifests naming this Problem

  • Jayyhk Erdős Leanjayyhk:erdos:619

Reported activity

Work these sources record against this Problem. Source-reported attribution, not reviewed here.

  • AI standalone

    Erdős AI contributions wiki · 9 Jun, 2026

    Machine
    Claude Fable 5, Codex, GPT-5.5
    Open the source record

  • construction

    VibeMathed

    Machine
    Claude Fable 5, Codex, GPT-5.5
    Reported outcome
    resolved
    Open the source record

Continue

Start a contributionBrowse the source filesOpen the collection entry

Search problems.science

Find a Problem, Result, source, or page