Task list filter?
Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.
Task rankings
Difficulty level
Task tags
Task type
«
«
Ramsey theorem for 2-colored graph
Task number: 4014
Prove that for every k∈N there exists n∈N such that for every graph G=(V,E) with at least n vertices and for each its edge coloring c:E→{1,2} there is U⊆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.