Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 17G (Graph Theory)

The diagonal Ramsey number $R(k)$ is the least $n$ such that every red-blue coloring of $K_n$ contains a monochromatic $K_k$. The standard recursiongivesThus the converted $k^4$ is a superscript-order error; that bound is false for large $k$.

In a red-blue coloring, if the red spanning graph is connected it has a red spanning tree. Otherwise its red components are joined pairwise by blue edges, making the blue graph connected, so it has a blue spanning tree.

The result fails for three colors. Color the six edges of $K_4$ by its three perfect matchings, one color per matching. Every monochromatic graph then consists of two disjoint edges and has no spanning tree.

A directed path of length two is determined by its middle vertex $x$ and an ordered pair of distinct neighbors, givingFor the colored complete graph, letA monochromatic triangle contributes three monochromatic two-edge angles to $S$, while a nonmonochromatic triangle contributes one. If $M$ and $N$ are their respective numbers, thenEliminating $N$ gives