There are 50 people at a party. Each person is (mutually) enemies with exactly 24 people. Show that if they all sit at a circular table, a seating is possible such that no 2 people who are enemies sit next to each other.
I am really not so sure how to approach this problem. I know that we should consider the graph with $50$ nodes. Then draw an edge between people if there are enemies. I think we need to somehow color the edges in some clever way but I cannot get it.
There is a similar problem here: A Problem about friends and strangers using Ramsey's Theory
All help is appreciated
Put an edge between the people which are not enemies. Then your task is finding a Hamilton circle in this graph. Each node has degree of 25, which is equal to $\frac{n}2$. According to Chvátal's Theorem, a Hamilton cycle exists in this graph.