Ramsey number recursion

ID: ramsey-number-recursion

Let and . From one vertex of any red-blue colored , either at least incident edges are red or at least are blue. In the first case, apply the definition of the Ramsey number to its red neighbors: a red extends with the chosen vertex, and a blue is already enough. The blue case is analogous. This proves the recursion, with boundary values and .

New to topics? Read the docs here!