Graphs and Their Complements
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 .
G
G
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.
K
4