Ramsey number for triangles ($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 giveThe 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 $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=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 $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges, giving $2^{15}=32768$ colorings. Checking all $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=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.

Place five labeled vertices around a pentagon. In the complete graph $K_5$, color the five perimeter edges red and the five diagonals blue. Writing $ij$ for the unordered pair $\{i,j\}$, the red pairs are $12,23,34,45,15$, and the blue pairs are $13,14,24,25,35$. This assigns a color to every pair, including every diagonal.

The red subgraph is the cycle graph $1,2,3,4,5,1$; the blue subgraph is the cycle graph $1,3,5,2,4,1$. Neither contains a triangle in a graph. Consequently, none of the ten triples has all three edges red or all three blue, proving the lower bound for the Ramsey number for triangles. Crossings in the drawing are not additional vertices.

Choose any vertex $v$ of a red-blue colored complete graph $K_6$. Its five incident edges go to the other five vertices. By the pigeonhole principle, at least three have the same color. Call their other endpoints $a,b,c$ and, after swapping color names if needed, suppose $va,vb,vc$ are red.

If any of $ab,ac,bc$ is red, it completes a red triangle in a graph with $v$. If none is red, all three are blue, so $a,b,c$ themselves form a blue triangle in a graph. Both possibilities force a monochromatic triangle in a graph. This proves the upper bound for the Ramsey number for triangles using only five incident edges and the three pairs among the selected neighbors; the colors of the other edges cannot defeat the argument.

Both panels show all 15 edges of a complete graph on six vertices. Faint colored edges are example choices outside the decisive argument; bold edges exhibit the forced triangle in a graph. The selected neighbor color could instead be blue, giving the same argument with the color names exchanged.