Edge additions for diameter four in triangle-free graphs

How many edges must be added to a connected triangle-free n-vertex graph to make its diameter at most four while preserving triangle-freeness? Can one always save a fixed linear fraction below n added edges?

Why it matters and what counts as progress

Why it matters: Graphs needing n−o(n) added edges would rule out every proposed fixed linear saving in this diameter-four completion problem.

What counts as progress: Prove a uniform saving or build graphs needing n−o(n) additions, with sharper quantitative error bounds.

How the problem developed

1998 · Open problem [1][2]
Paul Erdős, András Gyárfás, and Miklós Ruszinkó Asked whether every connected triangle-free n-vertex graph can be made diameter at most four by adding at most (1−ε)n edges while retaining triangle-freeness; proved bounds for target diameters three and five.
9 Jun 2026 · Counterexample claim [2][3]
Claude Fable 5, prompted by Nick Kuhn A construction reported on the problem thread gives connected triangle-free graphs requiring n−O(n^{8/9}(log n)^{2/9}) edge additions for diameter at most four; a Lean formalization is linked.

AI contribution

Claude counterexample refutes Erdős #619 diameter-four saving

For every η>0, a family of connected triangle-free graphs needs at least (1−η)n new edges to become diameter at most four while staying triangle-free. The problem record states the stronger quantitative bound h₄(G)≥n−O(n^(8/9)(log n)^(2/9)).

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (Lean 4 and comparator kernel check)

Human understandingFew