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.
The Ramsey number

is known to be 17, so

cannot be 3-colored without a monochromatic triangle.
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.