Problem

Source: Dutch IMO TST 2018 day 2 p4

Tags: combinatorics



In the classroom of at least four students the following holds: no matter which four of them take seats around a round table, there is always someone who either knows both of his neighbours, or does not know either of his neighbours. Prove that it is possible to divide the students into two groups such that in one of them, all students know one another, and in the other, none of the students know each other. (Note: if student A knows student B, then student B knows student A as well.)