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)<(1c)nh_4(G)<(1-c)n?

Workspace

Open this exact Problem, source revision, and authority Repository in Workbench. This handoff does not clone, switch, upload, or execute anything.

Canvas

public preview
  1. Source#619
  2. ResultNone
  3. Checks0

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

Search problems.science

Find a Problem, Result, source, or page