There are 20 people at a party and each one of them is friends with at least 10 of the people. They all sit at a round table. Prove that there is a way to place the people on the table, so that each one is friends with the person on his right and with the person on his left.
I am not sure if I understand this problem. Does it mean that each person must not know only one person? If that is the case, then we have a problem when n is odd. But then is it required that everyone must not know one person?
Can anyone clarify this question and give a hint as to how to prove it?
The problem tells us that for each pair of guests, a person at the dinner knows at least one of them. If you turn it into graph then it means that for any pair of two vertices, each of the remaining ones is adjacent to at least one of the two vertices in the pair.
On the other side the problem reduces to finding a Hamiltonian cycle in the graph. Such a cycle exists because of the Ore's Theorem.