= Solution
The diagonal <diagonal Ramsey number>[Ramsey number] $R(k)$ is the least $n$ such that every red-blue coloring of $K_n$ contains a monochromatic $K_k$. The standard recursion
$$
R(s,t)\leq R(s-1,t)+R(s,t-1)
$$
gives
$$
R(k)\leq\binom{2k-2}{k-1}<4^k.
$$
Thus 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.
Back to article page
