---

Claim. In the conventions of Problem 1011, $f_3(n)=\lfloor(n-1)^2/4\rfloor+2$ for every $n\ge5$: every graph on $n$ vertices with at least $\lfloor(n-1)^2/4\rfloor+2$ edges and chromatic number at least $3$ contains a triangle, and some triangle-free graph on $n$ vertices with chromatic number $3$ has $\lfloor(n-1)^2/4\rfloor+1$ edges. The claimed result is Lemma 1 of P. Erdős, On a theorem of Rademacher-Turán, Illinois J. Math. 6 (1962), no. 1, 122--127, p. 123: every graph on $n$ vertices with $\lfloor(n-1)^2/4\rfloor+2$ edges that is not "even" (not bipartite) contains a triangle, which Erdős says "was found jointly by Gallai and myself" and "was also found by Mr. Andrásfai independently"; and the example on p. 124, a triangle-free graph with a five-cycle whose edge count attains the proof's bound $\lfloor(n-1)^2/4\rfloor+1$ for every $n\ge5$ (the problem page states the example with its parameters, corrects a misprint in them and checks the count). For a triangle-free graph, chromatic number at least $3$ is the same as not bipartite, which is how the lemma answers the problem's $r=3$. The corpus states the lemma, the proof's bound and the example on its result page Lemma 1; Ren, Wang, Wang and Yang restate the bound as Theorem 1.2 of their preprint with the graph $H_0$ ([[../library/extremal_graph_theory/ren_2024_extremal_triangle_free_graphs_chromatic_number/theorem_1_2|Theorem 1.2]]). The claimant is Erdős, the paper's only author; he credits the lemma to joint work with Gallai and to Andrásfai independently, and the site's commentary credits Erdős and Gallai. The page's date is the issue's, 1 March 1962 (Crossref).

Covers. The value of $f_3(n)$ for every $n\ge5$; for $n\le4$ no triangle-free graph has chromatic number $3$ and the condition is vacuous. Nothing about $f_r(n)$ for any $r\ge4$, which the problem asks for as well; the problem stays open.

Depends on. No page of this wiki; the paper's lemma and example are the whole argument.

Acceptance. The paper is refereed: Illinois J. Math. 6 (1962), no. 1, 122--127, a journal publication, which is the refereed evidence. The site's commentary credits Erdős and Gallai with $f_3(n)$, but the site labels the problem OPEN, so the commentary is not acceptance of the problem and is not listed as reviewed. Read depth: the lemma, the attribution and the example were read clause by clause; the proof was read for structure, and the $k=2$ arithmetic of the example is an authored check on the problem page; nothing is independently reviewed by this project.