Problem 1558

Note that at most two segments of the same color start from any point. Otherwise there exist 4 points connected with the segments of the same color. But then either any of the other points are connected with these 4 points with the segments of the same color (it follows that all segments have the same color, which is impossible) or there exists a point connected with given 4 points with the segments of the remaining three colors. In this case this point is connected with at least two points with the segments of the same color (different from the color of the segment connected these two points), which is also impossible. So at most $2 \times 4 = 8$ segments start from any point. Since $(n-1)$ start from any point, we have $n-1 \le 8$, which gives $n \le 9$.

The example for $n = 9$. To each point assign one of the pairs $(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)$, and to each color assign one of the numbers $1,2,3,4$. Then three segments between points $(1,1), (1,2), (1,3)$, three segments between points $(2,1), (2,2), (2,3)$, and three segments between points $(3,1), (3,2), (3,3)$ we paint color 1; three segments between points $(1,1), (2,1), (3,1)$, three segments between points $(1,2), (2,2), (3,2)$, and three segments between points $(1,3), (2,3), (3,3)$ we paint color 2; three segments between points $(1,1), (2,2), (3,3)$, three segments between points $(1,2), (2,3), (3,1)$, and three segments between points $(1,3), (2,1), (3,2)$ we paint color 3; finally, three segments between points $(1,1), (2,3), (3,2)$, three segments between points $(1,2), (2,1), (3,3)$, and three segments between points $(1,3), (2,2), (3,1)$ we paint color 4.