Hrvatska 2011

It is known that a graph with $n$ vertices that contains no cycles has at most $n-1$ edges. That fact is easily proven by induction by the number of vertices $n$. Hence, at most $n-1$ edges (i.e. sides and diagonals) can be colored with the same color.

Since the number of colors is $k$ and the total number of edges (sides and diagonals) is $\frac{n(n-1)}{2}$, we conclude that $$\frac{n(n-1)}{2}\le (n-1)k,\text{i.e. }n\le 2k.$$ Let $k$ be an arbitrary positive integer. We will show that we can color the sides and diagonals of a regular $2k$-gon with $k$ colors so that there doesn't exist a closed monochrome broken line (without loss of generality we can assume that the polygon is regular because we only care how the edges are colored). Moreover, we will show that with each of the $k$ colors we can color exactly $2k-1$ sides and diagonals in the required way.

Let us denote the vertices of the regular $2k$-gon with $A_1,A_2,\dots ,A_{2k}$. With one color we color the broken line $A_1{A}_{2k}{A}_2{A}_{2k-1}\dots A_i{A}_{2k+1-i}\dots A_k{A}_{k+1}$, $2\le i\le k$, as shown on the picture below.



With each following color $j$, $j\in \{2,\dots ,k\}$ we color the broken line obtained by rotating the mentioned one by angle $\frac{j\pi }{k}$ around the center of the polygon.

The broken lines obtained in such a way are disjoint because otherwise one of the diagonals would be left unpainted, and that is not possible.

Therefore, the largest possible value of $n$ is $2k$.