In Exercises 1 and 2 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.
1. 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.
2. 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.