What is the minimum number of colors needed to color all vertices, sides, and diagonals of a convex $n$-gon, if the following two conditions must be satisfied:

1) any two segments emanating from the same vertex must be of different colors;
2) the color of any vertex must differ from the color of any segment emanating from it?
Since from each vertex $n-1$ segments come out and they all must be painted in different colors, distinct from the color of this vertex, the number of colors must be at least $n$.

We will prove that $n$ colors are sufficient. Let the vertices be denoted by $V_{0}, V_{1}, \ldots, V_{n-1}$, and the colors by the numbers $0,1, \ldots, n-1$. We will perform the coloring as follows: the segment $V_{i} V_{j}$ is painted with the color numbered $i+j(\bmod n)$, and the vertex $V_{i}$ is painted with the color numbered $2 i(\bmod n)$.

It is not difficult to verify that such a coloring satisfies the conditions of the problem.

## Answer

$n$ colors.

Send a comment