Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2014/6/b/ii/solution

Put , and consider any coloring of . Choose a vertex . Among its neighbors, either at least are joined to it by red edges, or at least by blue edges.
In the red case, the induced complete graph on those neighbors contains either a red , which joins with to make a red , or a blue . The blue case similarly gives a red or a blue which extends with to a blue . Hence every coloring has the required configuration, and
This is the Ramsey number recursion.

New to topics? Read the docs here!