Ramsey theorem for 2-colored graph

Task number: 4014

Prove that for every \( k \in \mathbb N \) there exists \( n \in \mathbb N \) such that for every graph \( G = (V, E) \) with at least \( n \) vertices and for each its edge coloring \( c: E \rightarrow \{1{,}2 \} \) there is \( U \subseteq V \) of size at least \( k \) such that all edges of the induced subgraph \( G [U] \) have the same color.

  • Solution

    We will complete the non-edges and color them arbitrarily. Then we apply the classical Ramsey theorem for two colors in the complete graph.

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