Ramsey(3,3,3)>16

permute the vertices

Color the edges

K

n

(the complete graph on

n

vertices) with three colors, red, green, and blue. When the Ramsey number

R(r,g,b)=n

, the graph will contain either a red

K

r

, a green

K

g

, or a blue

K

b

, and any smaller complete graph can be colored to avoid such subgraphs.

The Ramsey number

R(3,3,3)

is known to be 17, so

K

17

cannot be 3-colored without a monochromatic triangle.

This Demonstration shows that

K

16

can be 3-colored to be triangle free, proving that

R(3,3,3)>16

. Every pair of circles is connected in exactly one of the three Clebsch graphs, which together form

K

16

. Move the slider to permute the vertices.