Erdős problem 618

For a triangle-free graph $G$ let $h_2(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $2$ and is still triangle-free. Is it true that if $G$ has maximum degree $o(n^{1/2})$ then $h(G)=o(n^2)$ ?

Sources

The source's own material, retained exactly.

1 retained statement36c6d0fef71a

FormalConjectures/ErdosProblems/

618.lean

Retained formal statement1 of 1

For a triangle-free graph $G$ let $h_2(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $2$ and is still triangle-free. Is it true that if $G$ has maximum degree $o(n^{1/2})$ then $h(G)=o(n^2)$ ?

A problem of Erdős, Gyárfás, and Ruszinkó [EGR98]. Simonovits showed that there exist graphs $G$ with maximum degree $\gg n^{1/2}$ and $h_2(G)\gg n^2$ . Alon has observed this problem is essentially identical to [134], and his solution in this note also solves this problem in the affirmative.

FormalConjectures/ErdosProblems/618.leanErdos618.erdos_6185 linesExact file

1True ↔2  ∀ (G : (n : ℕ) → SimpleGraph (Fin n)),3    (∀ (n : ℕ), (G n).CliqueFree 3) →4      ((fun n => ↑(G n).maxDegree) =o[Filter.atTop] fun n => ↑n ^ (1 / 2)) →5        (fun n => ↑(Erdos618.h2 (G n))) =o[Filter.atTop] fun n => ↑n ^ 2

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.