Problem 619

For a triangle-free graph $G$ let $h_r(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $r$ (while preserving the property of being triangle-free).

Is it true that there exists a constant $c>0$ such that if $G$ is a connected graph on $n$ vertices then $h_4(G)<(1-c)n$ ?

Source: erdosproblems.com/619

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

SOLVED (LEAN), the site's label (snapshot of 5 September 2026); the resolution is negative, no such constant $c$ exists, so the frontmatter records the question as disproved. The standing is derived from the accepted claim page Kuhn's counterexample, whose acceptance evidence is the site's and formal-conjectures' documented acceptance; the corpus has not built the Lean proof, so no formalized evidence is listed.

Kuhn26: Nikolas Kuhn's counterexample, found by Claude Fable 5, with its Lean formalization.
AGR00: Noga Alon, András Gyárfás, and Miklós Ruszinkó, Decreasing the Diameter of Bounded Degree Graphs.
EGR98: Paul Erdős, András Gyárfás, and Miklós Ruszinkó, How to Decrease the Diameter of Triangle-Free Graphs, Combinatorica 18(4) (1998), 493--501.
Er99: Paul Erdős, A Selection of Problems and Results in Combinatorics, Combinatorics, Probability and Computing 8(1--2) (1999), 1--6, DOI 10.1017/S0963548398003496. - Gonzalo Fiz Pontiveros, Simon Griffiths, and Robert Morris, *The triangle-free process and the Ramsey number $R(3,k)$ . - Elena Grigorescu, Decreasing the Diameter of Cycles.

Problem 619

Status

Proof claims

Discussion