Ramsey(3,3,3)>16
Ramsey(3,3,3)>16
Color the edges (the complete graph on vertices) with three colors, red, green, and blue. When the Ramsey number , the graph will contain either a red , a green , or a blue , and any smaller complete graph can be colored to avoid such subgraphs.
K
n
n
R(r,g,b)=n
K
r
K
g
K
b
The Ramsey number is known to be 17, so cannot be 3-colored without a monochromatic triangle.
R(3,3,3)
K
17
This Demonstration shows that can be 3-colored to be triangle free, proving that . Every pair of circles is connected in exactly one of the three Clebsch graphs, which together form . Move the slider to permute the vertices.
K
16
R(3,3,3)>16
K
16