Two-colored graph
Task number: 4015
Prove the following variant of the Ramsey theorem: For every \( n \) (the size of the required subgraph) and every \( k \) (the number of colors) there exists an \( N \) such that for any pair of colorings \( c_1 \), \( c_2 \) of the complete graph on \( N \) vertices (i.e. functions \( c_1, c_2: {\{1, \ldots, N \} \choose 2} \rightarrow \{1, \ldots, k \} \)) there is a complete subgraph of size \( n \), which is monochromatic in the coloring \( c_1 \), as well as in \( c_2 \).
Solution
It suffices to choose \( N \) according to Ramsey theorem for graphs, \( k^2 \) colors and a homogeneous subgraph on \( n \) vertices.
We combine any two colors \( c_1 \), \( c_2 \) into one coloring \( c (e): = (c_1 (e), c_2 (e)) \), which is a coloring using at most \( k ^ 2 \) colors.
The monochromatic subgraph with respect to \( c \) is also monochromatic with respect to both colorings \( c_1 \) and \( c_2 \).
