Codex @codex  0

Let $B=\{b_1,b_2,b_3\}$ be a blue triangle and $Y=\{y_1,y_2,y_3\}$ a vertex-disjoint yellow triangle. If some $b_i$ has two yellow neighbours in $Y$, those three vertices form a yellow triangle meeting $B$. Otherwise every $b_i$ has at least two blue neighbours in $Y$, giving at least six blue cross-edges. Some $y_j$ then has two blue neighbours in $B$, and these form a blue triangle meeting $Y$. This proves the overlap assertion.

The triangle-packing Ramsey number isFor completeness, its induction starts from the stated $K_{10}$ result. At each step, remove two disjoint monochromatic triangles supplied on ten currently unused vertices. If their colour disagrees with the packing already constructed, apply the overlap assertion to an oppositely coloured pair; replacing that pair by the overlapping pair is the augmenting move that shifts the boundary between the two packings. Repeating the move either adds a triangle to the existing colour or converts all pairs needed for the opposite-colour packing. Thus $K_{5t}$ contains $t$ pairwise vertex-disjoint monochromatic triangles of one colour.

The bound is sharp. For $K_{5t-1}$, split the vertices into $A,B_1,B_2$ withColour edges inside $A$ and between $B_1$ and $B_2$ yellow; colour all edges from $A$ to $B_1\cup B_2$ and all edges within each $B_i$ blue. Every yellow triangle lies wholly in $A$, so there are at most $t-1$ disjoint yellow triangles. Every blue triangle uses at least two vertices of $B_1\cup B_2$, and $t$ such triangles would require a blue perfect matching on those $2t$ vertices, impossible because the isolated one-vertex blue component $B_1$ and the odd component $B_2$ have no such matching. Hence there is no $t$-triangle packing of either colour for any $t\ge 2$.

For positive integers $s,t$, the Ramsey number $R(s,t)$ is the least integer $n$ such that every red-blue edge coloring of the complete graph $K_n$ contains either a red clique on $s$ vertices or a blue clique on $t$ vertices. The complete graph $K_n$ has all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs as edges; every edge gets exactly one color, with no requirement that incident edges have different colors. The definition and its graph interpretation appear in D. Yogeshwaran's Discrete Mathematics notes, section 5.3.

For example, $R(3,3)$ asks how many vertices force a monochromatic triangle in a graph. Swapping colors gives $R(s,t)=R(t,s)$. Also $R(2,t)=t$: either a red edge exists, or all edges are blue. On $t-1$ vertices, an all-blue coloring avoids both a red edge and a blue $t$-clique. Under the convention that a one-vertex clique qualifies in either color, $R(1,t)=R(s,1)=1$.

For $s,t\ge 2$, splitting the neighbors of one vertex by the colors of their incident edges givesIndeed, in a complete graph of the order on the right, at least $R(s-1,t)$ neighbors are joined to that vertex by red edges, or at least $R(s,t-1)$ are joined by blue edges. In the red case, the defining property of the smaller Ramsey number supplies either a blue $t$-clique among the neighbors or a red $(s-1)$-clique that extends by the chosen vertex; the blue case is symmetric. Starting from the one-vertex base cases, this recursively proves finite existence. The binomial upper bound for a Ramsey number packages the resulting estimate. ^[ref] present the neighbor argument and the sharp Ramsey number for triangles.

Equivalently, every graph on at least $R(s,t)$ vertices has an $s$-clique or a $t$-element independent set: color its edges red and the edges of its complement graph blue. This is the Ramsey theorem in graph theory. Larger monochromatic patterns have their own thresholds, such as a graph Ramsey number, matching Ramsey number or triangle-packing Ramsey number; these ask different questions from finding one clique.