= Ramsey number for triangles
{c}
{title2=$R(3,3)=6$}
Every red-blue <edge coloring> of the <complete graph> $K_6$ contains a <monochromatic> <triangle in a graph>, and some coloring of $K_5$ contains none. Together the <five-cycle Ramsey coloring> and <six-vertex monochromatic triangle argument> give
$$
5<R(3,3)\leq6,\qquad R(3,3)=6.
$$
The threshold is exact: one carefully chosen coloring establishes the lower bound, while the upper bound must handle every coloring.
A familiar interpretation uses six people and colors each pair red if they know one another and blue if they do not. Assuming the relation is symmetric and every pair falls into exactly one case, there are either three mutual acquaintances or three mutual strangers. The conclusion concerns all three pairs within the group, not merely two relationships through a common person. There is no prediction about which color wins or which three people form the group.
The small size makes exhaustive verification practical. The <complete graph> $K_5$ has $\binom52=10$ <edges>, giving $2^{10}=1024$ red-blue colorings of labeled <vertices>; exactly 12 have no <monochromatic> <triangle in a graph>. They are the choices of a red <cycle graph> of length five, whose blue <complement graph> is another five-cycle. The <complete graph> $K_6$ has $\binom62=15$ <edges>, giving $2^{15}=32768$ colorings. Checking all $\binom63=20$ triples in every coloring finds none without a <monochromatic> <triangle in a graph>; in fact the minimum number is two. These counts can be reproduced by assigning one <bit> to each <unordered pair> and testing whether the three <bits> of each triple agree. The <monochromatic-triangle counting formula> gives a separate explanation of the stronger minimum-two conclusion.
Back to article page
