What is a Graph? · Graphs

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

Let us enumerate all the cells of a \(3\times 3\) board except for the middle one (which is not reachable by any of the four knights in any case).

Now, if a knight can get from one cell to another one (in a single move), we connect them by a line.

This gives us a graph! After staring at it for some time, we realize that the exact positions of the circles are not that important. This observation allows us to untangle this graph to get the following drawing (of the same graph!).

In terms of this graph, our problem can be restated as follows:

From this picture, it is already not difficult to see that the mission is possible: one can move all four knights along the circle (say, clockwise) four times.