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.
