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.

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