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
Suppose that are eight knights Alynore, Bedivere, Degore, Gareth, Kay, Lancelot, Perceval, and Tristan. Their lists of enemies are A (D, G, P), B (K, P, T), D (A, G, L), G (A, D, T), K (B, L, P), L (D, K, T), P (A, B, K), T (B, G, L), where we have represented each knight by the first letter of his name and shown the list of enemies of that knight following this first letter. Draw the graph representing these eight knight and their friends and find a seating arrangement where each knight sits next to two friends.