Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A / 3

The Ramsey number $R(k,l)$ is the least $N$ such that every graph on $N$ vertices has a $k$-clique or an independent set of size $l$. Choose a vertex in a graph of order $R(k-1,l)+R(k,l-1)$. It has either at least $R(k-1,l)$ neighbours or at least $R(k,l-1)$ nonneighbours. In the first set, a $(k-1)$-clique extends with the vertex to a $k$-clique, while an independent $l$-set already suffices. The complementary argument handles the second set. ThusThe boundary values are $R(k,2)=k$ and $R(2,l)=l$. Induction on $k+l$, using Pascal's identity, therefore gives

The graph Ramsey number $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$.

For $s,t\ge 2$, split $(s-1)(t-1)$ vertices into $s-1$ classes of size $t-1$, coloring edges between classes red and edges inside classes blue. The red graph has no $K_s$, and every blue component is too small for the connected tree. This proves the lower bound.

For the upper bound let $N=(s-1)(t-1)+1$ and suppose the blue graph contains no copy of the tree. By the permitted chromatic-number statement, its chromatic number is at most $t-1$. A graph of larger chromatic number would have a subgraph of chromatic number exactly $t$, obtained by deleting vertices until that number is reached. A proper blue coloring with at most $t-1$ classes puts no blue edges within any class, so each class is a red clique. If there is no red $K_s$, each class has at most $s-1$ vertices, contradicting $N>(s-1)(t-1)$. ThereforeThe one-vertex boundary cases give one directly.

A vertex with at least $R(t,t)$ neighbours has either a $t$-clique among them, producing $K_{t+1}$ with the vertex, or an independent $t$-set among them, producing an induced star with that centre.

For the second assertion put $D=R(t,t)-1$. If either of those two outcomes is absent, the preceding result forces maximum degree at most $D$. In a connected graph of this maximum degree, a ball of radius $t-1$ has at most $1+D+\cdots +D^{t-1}$ vertices, using the rough bound on walks at each distance. If the graph has more vertices, some vertex lies at distance at least $t$ from a chosen root. A shortest path to it is induced, since a chord would shorten it; its first $t$ edges give an induced path of the required length. Thus a sufficiently large connected graph has one of the three listed configurations.