 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2007/a/3/b/solution

R (G, H)

is the smallest

N

such that every red-blue coloring of the edges of

K_{N}

has a red copy of

G

or a blue copy of

H

. These copies are subgraphs, not necessarily induced. Equivalently every graph on

N

vertices contains

G

or its complement contains

H

 New to topics? Read the docs here!