Ramsey theorem for vertices
Task number: 4205
Prove that for every positive integer \( k \) there exists a positive integer \( n \) with the following property. If the vertices of the complete graph \( K_n \) are colored with 14 colors, then there are \( k \) vertices that have the same color.
Solution
According to Dirichlet’s principle, it is enough to take \( n = 14k-13 \), then some of the 14 subsets will contain at least \( k \) vertices.
The edges of the graph are irrelevant.
