Belorusija 2012

Answer: $k=5$.

First we show that for $1\le k\le 4$ the required colouring does not exist.

1. There is nothing to prove for $k=1$ and $k=2$.

2. Let $k=3$. Consider one (say $A$) of these 10 points. We have 3 colours and 9 segments connecting $A$ with other points. So there are two segments (say $AB$ and $AC$) having the same colour. Therefore, the edges of the graph with vertices $A$, $B$, and $C$ are painted at most 2 colours, thus the required colouring does not exist.

3. Let $k=4$. Suppose that there is a point $A$ such that at least 4 segments (say, $AB$, $AC$, $AD$, and $AE$, see Fig. 1) have the same colour (call it blue). Then among the segments connecting points $B$, $C$, $D$, and $E$ there is at least one blue segment (say, $BD$). In this case, there are four blue segments $AB$, $AC$, $AD$, $BD$ and we have to use three different colours to paint two segments $BC$ and $CD$, which is impossible.

Fig. 1 Fig. 2

Hence if the required colouring is possible, then at most 3 segments from any point have the same colour. This yields that for any point (take one of them, say, $A$) there is a colour (say, blue) such that there are exactly three (say, $AB$, $AC$, $AD$, see Fig. 2) blue segments from $A$. Then none of the segments $BC$, $CD$, $BD$ is blue, otherwise $A$, $B$, $C$, $D$ would give a contradiction. For any three points of points $K$, $E$, $F$, $G$, and $H$ among the segments connecting these three points there is a blue segment, otherwise there is no blue segment among the segments connecting $A$ and these three points. (This is a variant of the well-known lemma: among any six persons there are either three pairwise acquainted or three pairwise not acquainted.) Thus there are three points (say, $K$, $E$, $F$) such that all segments $KE$, $KF$, $EF$ are blue. There is at least one blue segment (say, $BK$) among segments $BK$, $CK$, $DK$ (otherwise there is no blue segment among the segments connecting points $B$, $C$, $D$, and $K$). It is sufficient to consider points $B$, $K$, $E$, and $F$ to obtain a contradiction. Therefore the required colouring is impossible for $k=4$.

4. It remains to consider the case when $k=5$. We present a complete graph with 10 vertices as a disjoint union of 5 graphs (Fig. 3) that are isomorphic to the graph on Fig. 4 and paint each of these graphs its own colour (different from others). It is easy to see that 1) each vertex is the end of the segments of all 5 colours: there are 3 segments having the first colour, 3 segments having the second colour, and 3 segments painted with remaining 3 colours; 2) there are exactly 9 segments of the same colour; 3) each monochromatic graph is isomorphic to the graph on Fig. 4. Therefore for $k=5$ the required colouring is possible.

	0	1	2	3	4	5	6	7	8	9
0		5	1	4	4	1	1	4	3	2
1	5		2	3	2	3	4	1	2	3
2	1	2		5	2	1	1	3	2	4
3	4	3	5		4	3	2	4	1	3
4	4	2	2	4		5	3	4	2	1
5	1	3	1	3	5		1	2	4	3
6	1	4	1	2	3	1		5	5	5
7	4	1	3	4	4	2	5		5	5
8	3	2	2	1	2	4	5	5		5
9	2	3	4	3	1	3	5	5	5

Fig. 3