Question: We consider a puzzle posed by Petkovi´c in [Pe09] (based on a problem in [AvCh80]). Suppose that King Arthur has gathered his 2n knights of the Round Table for an important council. Every two knights are either friends or enemies, and each knight has no more than n - 1 enemies among the other 2n - 1 knights. The puzzle asks whether King Arthur can seat his knights around the Round Table so that each knight has two friends for his neighbors
a) Show that the puzzle can be reduced to determining whether there is a Hamilton circuit in the graph in which each knight is represented by a vertex and two knights are connected in the graph if they are friends.
b) Answer the question posed in the puzzle.