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.



  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.