Graphs and Their Complements

Check or uncheck the boxes to color edges blue or orange. (The boxes on the main diagonal are for counting, but don't do anything.) You can think of the blue edges as the edges of a graph and the orange edges as the edges of the graph complement of .
Ramsey's theorem deals with the minimum number of vertices needed to ensure that certain colored subgraphs are forced to appear in a multicolored graph. For example, the simplest case states that a graph on six vertices with blue or orange edges either has a blue triangle or an orange triangle, and that this is not necessarily true for five vertices. The next case, either having a blue triangle or an orange quadrangle (a subgraph), requires nine vertices.

THINGS TO TRY

SNAPSHOTS

  • [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.