Jirka drew a square grid with 25 squares, see the image. Then he wanted to color each square so that squares of the same color do not share any vertex.

How many colors did Jirka need at least?

(M. Dillingerová)

![](https://cdn.mathpix.com/cropped/2024_04_17_adee0188cf1f8dcaeca5g-4.jpg?height=383&width=380&top_left_y=485&top_left_x=838)

Hint. Start in one of the corner squares.
If the top-left square is colored with some color, the surrounding three squares must be colored with mutually different colors. Jirka had to use at least 4 colors, which we will denote by the digits from 1 to 4:

| 1 | 2 |  |  |  |
| :--- | :--- | :--- | :--- | :--- |
| 4 | 3 |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |

Now we need to determine whether four colors are sufficient to color the rest of the grid according to the given rules, or not. We will gradually find out that four colors are indeed sufficient:

| 1 | 2 | 1 | 2 | 1 |
| :--- | :--- | :--- | :--- | :--- |
| 4 | 3 | 4 | 3 | 4 |
| 1 | 2 | 1 | 2 | 1 |
| 4 | 3 | 4 | 3 | 4 |
| 1 | 2 | 1 | 2 | 1 |