Graphs and Their Complements

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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 .

[more]

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.

[less]

Contributed by: George Beck and Ed Pegg Jr (March 2011)
Open content licensed under CC BY-NC-SA


Snapshots


Details



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send