---

Claim. Both constants in the known bounds on $F(n)$ of Problem 1182 are improved: $F(n)\ge n+\lfloor(n-1)/6\rfloor$ for every $n\ge4$, where the 1980 theorem of Burr, Erdős, Faudree, Rousseau and Schelp gives $(17n+1)/15$, and $F(n)\le11n/2$, sharpened to $F(n)\le5.03n$, for all large $n$, where Brandt gives $84n$.

The lower bound reuses the 1980 argument, which strips a sparse connected graph down to a dense core and bounds the Ramsey number of the core, and feeds it Sidorenko's theorem $R(K_3,H)\le2e(H)+1$, a sharper input than the 1980 paper had; with it the arithmetic tolerates a core of up to $6k$ edges whenever $k\le(n-1)/6$, and every connected graph with at most $n+\lfloor(n-1)/6\rfloor$ edges stays triangle-good.

The upper bound exhibits, for large $n$, connected graphs with about $11n/2$ edges that are not triangle-good, namely almost all $11$-regular graphs $H$ on $n$ vertices. The witness coloring of $K_{2n-1}$ takes a balanced blow-up of $C_5$, which has no triangle, as its red graph; $H$ is a blue subgraph exactly when its vertices can be partitioned into the five blow-up classes, each of size at most $\lceil(2n-1)/5\rceil$, with no edge of $H$ joining two classes consecutive on the pentagon. The claimant computes the expected number of such partitions of a random $d$-regular graph as $\exp(n\max\Psi_d+o(n))$ for an explicit function $\Psi_d$ and shows $\max\Psi_{11}\le-0.05$ by a branch-and-bound search over the domain of $\Psi_{11}$ in exact arithmetic, pruned by a dual bound and a convexity argument; the expectation then tends to zero, so almost every $11$-regular graph has no blue copy and $R(K_3,H)>2n-1$. For the $5.03n$ bound a random $10$-regular graph with $0.03n$ random edges added takes the place of $H$; the claimant notes that $d=10$ alone falls short and that about $5.02n$ is the method's limit.

Submission note. Posted to erdosproblems.com as a proof claim by Pravar Kataria (account pravarkataria) on 29 September 2026, giving "Claude Fable 5.1 (Anthropic)" as the AI used:

Improved constants: $n+\lfloor (n-1)/6\rfloor \le F(n)$ for $n\ge4$, and $F(n)\le 11n/2$ (indeed $\le 5.03n$) for large $n$; the page records $17n/15$ and $84n$. Lower bound: the [BEFRS80] reduction leaves a core with at most $6k$ edges; Sidorenko's $R(K_3,H)\le 2e(H)+1$ replaces their weaker bound, so $12k+1\le 2n-1$ for $k\le (n-1)/6$. Upper bound: $H$ embeds in the complement of the balanced $C_5$ blow-up on $2n-1$ vertices iff $V(H)$ splits into five classes of size $\le\lceil(2n-1)/5\rceil$ with no edge between classes adjacent in $C_5$. For a random $d$-regular graph the expected number of splittings is $e^{n\max\Psi_d+o(n)}$; a dual bound plus convexity gives a branch and bound certifying $\Psi_{11}\le-0.05$ (exact arithmetic). So a random 11-regular graph is a.a.s. not good. Notes: AI use: the arguments, code and write-up were produced by Claude Fable 5.1 (Anthropic) under my direction. I have reviewed them and re-run the certificate myself. Unrefereed; corrections welcome, as is a pointer if either bound is already known. A random 10-regular graph plus 0.03n random edges gives 5.03n; d = 10 alone fails (exponent about +0.003), so about 5.02n is the limit of the method. The note's appendix gives the certificate algorithm, full output and rounding argument. Code, results, logs: https://github.com/Sovi11/erdos-1182; key check: python code/certify_exact.py 11 0.401 0.05 (about 30 s).

Covers. The constants: if the claim holds, $7/6\le\liminf F(n)/n$ and $\limsup F(n)/n\le5.03$, against the $17/15$ and $84$ of the problem page, and the closing question's negative answer follows again, independently of Brandt 1996; as on that page, the claim value follows the closing question's polarity, a no to "is it true that $F(n)/n\to\infty$?". The order of $f(n)$ and the exact growth of $F(n)$ are not addressed.

Depends on. Burr, Erdős, Faudree, Rousseau and Schelp 1980 for the reduction the lower bound reuses; the lower bound also rests on Sidorenko's theorem, the upper bound on the certificate in the repository.

Standing. Claimed. The page rests on the repository's README and the proof claim; the note itself is not compiled and the certificate was not re-run, so no evidence kind is listed. The claim's notes declare that the arguments, code and write-up were produced by Claude Fable 5.1 (Anthropic) under the author's direction, who reviewed them and re-ran the certificate, and that the work is unrefereed; that is provenance only. The claim has no comments, and the site's label (OPEN) and commentary are unchanged. The repository was created on 28 September 2026, the date this page is named by; the claimant's thread comment of the same day reports that both functions are tabulated exactly for $n\le12$ from the Ramsey numbers of Brandt, Brinkmann and Harmuth, All Ramsey numbers $r(K_3,G)$ for connected graphs of order 9, Electron. J. Combin. 5 (1998), R7 (cited from the journal's record; its abstract gives $r(K_3,G)$ for every connected graph of order $9$ and for some graphs up to order $12$, and the comment's reading of its tables is unchecked against the paper), with an independent recomputation through $n=9$ and certificates for $F(13)\le24$ through $F(18)\le44$. That literature pointer and those computations are not part of the proof claim and are not carded here.