: Let $n$ be a positive integer. Each cell of an $n \times n$ table is coloured in one of $k$ colours where every colour is used at least once. Two different colours $A$ and $B$ are said to touch each other, if there exists a cell coloured in $A$ sharing a side with a cell coloured in $B$. The table is coloured in such a way that each colour touches at most 2 other colours. What is the maximal value of $k$ in terms of $n$ ?
$k=2 n-1$ when $n \neq 2$ and $k=4$ when $n=2$.

$k=2 n-1$ is possible by colouring diagonally as shown in the figure below and when $n=2, k=4$ is possible by colouring each cell in a unique colour.

![](https://cdn.mathpix.com/cropped/2024_04_17_4ead9738494cc20c28d3g-09.jpg?height=214&width=217&top_left_y=1024&top_left_x=925)

We consider the graph, where each node represents a colour and two nodes are linked, if the colours they represent touch. This graph is connected and since each colour touches at most 2 colours every node has at most degree 2 . This means that the graph is either one long chain or one big cycle.

![](https://cdn.mathpix.com/cropped/2024_04_17_4ead9738494cc20c28d3g-09.jpg?height=146&width=534&top_left_y=1486&top_left_x=767)

We now look at the case when $n$ is odd. Consider the cell in the center of the table. From this cell we can get to any other cell by passing through at most $n-1$ cells. Therefore from the node representing this cell, we can get to any node through at most $n-1$ edges. But if the graph has $2 n$ or more nodes, then for every node there is a node which is more than $n-1$ edges away. So we must have $k \leq 2 n-1$ for all odd $n$.

When $n$ is even we consider the 4 center cells. If they all have a different colour, then they form a 4-cycle in the graph, meaning the graph has only 4 nodes. If two of the center cells have the same colour, then from this colour you will be able to get to all other cells passing thorugh at most $n-1$ cells. By same the arguments as in the odd case, we get $k \leq \max (2 n-1,4)$ for even $n$.

So overall we have $k \leq 2 n-1$ for $n \neq 2$ and $k \leq 4$ for $n=2$ as desired.