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?
Retained from Formal Conjectures · not edited here
Formal statements
5 solved · 2 test
Erdős Problems says
solved (Lean)
Decision here
No current contribution
Checks
0 checks · 7 formal

Current Result

Accepted in Vela Mathematics Program

Current Result

No result has been accepted here yet.

Type
Evidence
0 artifacts
Decision
None
Reviewed
No date retained

Search problems.science

Find a Problem, Result, source, or page