---

Claim. In the letters of Problem 1182, $F(n)<84n$ for all sufficiently large $n$. Brandt proves that for almost every $d$-regular graph $H$ of order $n$ with $d\ge168$ the Ramsey number $R(K_3,H)$ exceeds $2n$: the complement of a lexicographic product $C_5[\overline{K_r}]$ on $2n$ or more vertices contains no well-expanding graph, and almost every such $H$ expands well. Such a graph is connected with $84n$ edges and is not triangle-good, so the threshold $F(n)$ below which every connected $n$-vertex graph is triangle-good is below $84n$. Since Burr, Erdős, Faudree, Rousseau and Schelp 1980 proved $F(n)\ge(17n+1)/15$ for $n\ge4$, the ratio $F(n)/n$ stays between $17/15$ and $84$ for large $n$ and does not tend to infinity. The bound is paged at bound_p7 of the library's source card, which names the copy read, a conversion of the preprint's PostScript that the library does not hold (preprint pp. 4 and 7--8). Brandt adds, without proof, that a refined analysis gives $F(n)/n<11.75$ and that he expects $2<F(n)/n<6$ for large $n$; those are the author's remarks, not part of the claim.

Covers. The closing question of the problem, whether $F(n)/n\to\infty$: the answer is no. The estimation of $F(n)$ and $f(n)$, the problem's main question, is not settled; with this bound $F(n)$ lies only between $17n/15$ and $84n$ for large $n$, and $f(n)$ only between $n^{3/2}(\log n)^{1/2}$ and $n^{3/2}\log n$ up to constants, the upper bound from Sudakov 2007.

Depends on. Burr, Erdős, Faudree, Rousseau and Schelp 1980 for the lower bound that makes the ratio bounded below; the upper bound rests on the cited preprint (bound_p7).

Standing. Claimed. The site's curator, T. F. Bloom, cites Brandt's bound in the commentary as the improvement of the 1980 upper bound and notes that it answers the final question in the negative (page last edited 11 April 2026, after the thread of 14--15 March 2026 in which a reader, unable to find the paper online, reconstructed the preprint in LaTeX and pointed out that the linear bound answers the question). The site labels the problem OPEN, and commentary under that label is not acceptance, so reviewed is not listed. The preprint has no journal version (Crossref bibliographic query, 2026-09-18), so refereed is not listed, and no formalization of the bound is known. The argument is compiled for structure on the library card and not checked; its input on the expansion of random regular graphs is the preprint's Theorem 3.

Postings. The preprint on the Freie Universität Berlin preprint server (PostScript, linked from the site's thread), dated by month only, December 1996, so the day in this page's name and in the link's date is the month's first; the site's problem page and thread. The thread also links a third party's LaTeX reconstruction, which is not the author's posting and is not linked here.