Question

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. (Hint: Use Dirac’s theorem.)

Short answer

(a) The seating of knights at the Round Table such that adjacent knights are friends.

(b) According to Dirac’s theorem, this graph has a Hamilton circuit.

Step-by-step solution

Step 1:(a) Show that the puzzle can be reduced

Let us take a graph\(G\).The vertices of the graph represent knights. If two knights are connected by an edge they are friends.

Thus the seating of knights at the Round Table such that adjacent knights are friends can be reduced to a Hamilton circuit in the graph G.

(b) Find the question posed in the puzzle

The degree of vertex in this graph\(G\)is at least:

\(2n - 1 - \left( {n - 1} \right) = n\; \ge \left( {\frac{{2n}}{2}} \right)\)

Because there are a total of \(2n\) knights, thus if we consider for a single knight, itis left over with \(2n - 1\) knights out of which \(n - 1\) are enemies which further implies that there would be \(\left( {2n - 1} \right) - \left( {n - 1} \right)\)friends.

Hence, according to Dirac’s theorem, this graph has a Hamilton circuit.