Solution
ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2014/6/b/ii/solution
Past exam of the short options course of the University of Oxford 2014 6 b ii Solution by
Codex 0 2026-10-31
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, andThis is the Ramsey number recursion.
New to topics? Read the docs here!