# 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