Status
On this page
Status
Topics
Status
On this page
Status
Topics
For a triangle-free graph let be the smallest number of edges that need to be added to so that it has diameter and is still triangle-free. Is it true that if has maximum degree then ?
For a triangle-free graph let be the smallest number of edges that need to be added to so that it has diameter and is still triangle-free. Is it true that if has maximum degree then ?
Source: erdosproblems.com/618
An accepted solution exists. The statement is true.
PROVED (LEAN). The site's label credits Alon's note with the
solution, and the frontmatter standing is derived from the accepted claim page
Alon's theorem,
whose acceptance evidence is the site's own. The Lean part of the label refers
to the formalization of Alon's solution whose header names Aristotle and
Alexeev as formal authors, linked from that claim page; the corpus has not
built that Lean file, so it gives no formalized evidence. The standing
judges the corrected Statement.
The site's wording defines and then asks about , which it never defines, so the question is undefined for every graph. The change replaces "" in the question by "". The evidence is the posers' own text: Erdős, Gyárfás and Ruszinkó [EGR98], p. 493, let be the least number of edges whose addition gives a maximal triangle-free extension, that is a triangle-free graph on the same vertex set of diameter at most two, and write ""; their Problem 4.1 (pp. 498--499) asks the question in terms of . So the site's is the posers' name for the site's , and the defect is the site's: it renamed the function in the definition but not in the question. The site's "diameter " differs from the source's "diameter at most two" but changes nothing: for a triangle-free completion of diameter at most two cannot have diameter one, since it would then be a complete graph containing a triangle, and the question is asymptotic in . No result about the site's wording is recorded.