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 \).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email