---

Claim. For every graph $H$ with $m\ge1$ edges and no isolated vertices,

$$R(K_3,H)\le2m+1\le3m,$$

so in the notation of Problem 569 $c_1\le3$. The one-edge graph $K_2$ is eligible and $R(C_3,K_2)=3$: on two vertices there is no triangle, and on three vertices a coloring with no blue edge is an all-red triangle. So $c_1\ge3$, and hence $c_1=3$. The theorem is paged as the main theorem of the library's source card. Sidorenko proved the same theorem independently (Sidorenko 1993); the same theorem is the case $k=3$ of Problem 570, recorded on its claim page there. A comment of 27 March 2026 in the site's discussion thread credits the case $k=1$ to this paper and to Sidorenko.

Covers. The case $k=1$, $c_1=3$. Nothing about $k\ge2$.

Depends on. Nothing in this wiki; the result rests on the cited paper, and the one-edge endpoint is elementary.

Acceptance. Refereed: W. Goddard and D. J. Kleitman, An upper bound for the Ramsey numbers $r(K_3,G)$, Discrete Math. 125 (1994), no. 1--3, 177--182, in the February 1994 issue, the month this page is dated by; the day is a placeholder. The site labels the problem OPEN, so its pages are not acceptance.

Read depth. The statement on p. 1 of the author manuscript described on the source card was checked against the problem's formula; the proof was not checked. Nothing is independently reviewed in this corpus.