Variants of Ramsey theorem

Task number: 4016

Decide which of the following statements are true:

  • Variant

    For every positive integer \( n \) there exists a positive integer \( N \) such that if the vertices of the complete graph \( K_N \) are colored with two colors, then in the considered graph exists a complete subgraph \( K_n \) whose all vertices are colored with the same color.

  • Variant

    If we color a sufficiently large complete graph with loops with two colors (we color edges and loops), there is always a monocromatic complete subgraph with loops on \( n \) vertices.

  • Variant

    For every positive integer \( n \) there exists a positive integer \( N \) such that for any graph \( G \) on \( N \) vertices holds: either \( G \) contains \( K_{n,n} \) as a subgraph or the complement of \( G \) contains \( K_{n,n} \) as a subgraph. Considered subgraph need not to be induced.

  • Variant

    For every positive integer \( n \) there exists a positive integer \( N \) such that for any graph \( G \) on \( N \) vertices holds: either \( G \) contains \( K_{n,n} \) as a subgraph or \( G \) contains the complement of \( K_{n,n} \) as a subgraph. Considered subgraph need not to be induced.

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