Ramsey’s theorem states that for any complete graph, there exists some number such that any edge 2-coloring yields a complete subgraph of that size in one of the colors, or informally, “complete disorder is impossible”.
June 21, 2017—Dennis Hou
Friends and Strangers
We begin by looking a famous special case of Ramsey’s theorem (the theorem on friends and strangers) which states that in a group of six people, either three people mutually know each other or three people mutually do not know each other.
Make a complete graph with six vertices:
In[]:=
CompleteGraph[6]
Out[]=
The theorem begins with six people at a party, so we label each vertex to represent a person.