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.
Browse all topics
