, 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.

<table>
<thead>
<tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th></tr>
</thead>
<tbody>
<tr><th>0</th><td></td><td>5</td><td>1</td><td>4</td><td>4</td><td>1</td><td>1</td><td>4</td><td>3</td><td>2</td></tr>
<tr><th>1</th><td>5</td><td></td><td>2</td><td>3</td><td>2</td><td>3</td><td>4</td><td>1</td><td>2</td><td>3</td></tr>
<tr><th>2</th><td>1</td><td>2</td><td></td><td>5</td><td>2</td><td>1</td><td>1</td><td>3</td><td>2</td><td>4</td></tr>
<tr><th>3</th><td>4</td><td>3</td><td>5</td><td></td><td>4</td><td>3</td><td>2</td><td>4</td><td>1</td><td>3</td></tr>
<tr><th>4</th><td>4</td><td>2</td><td>2</td><td>4</td><td></td><td>5</td><td>3</td><td>4</td><td>2</td><td>1</td></tr>
<tr><th>5</th><td>1</td><td>3</td><td>1</td><td>3</td><td>5</td><td></td><td>1</td><td>2</td><td>4</td><td>3</td></tr>
<tr><th>6</th><td>1</td><td>4</td><td>1</td><td>2</td><td>3</td><td>1</td><td></td><td>5</td><td>5</td><td>5</td></tr>
<tr><th>7</th><td>4</td><td>1</td><td>3</td><td>4</td><td>4</td><td>2</td><td>5</td><td></td><td>5</td><td>5</td></tr>
<tr><th>8</th><td>3</td><td>2</td><td>2</td><td>1</td><td>2</td><td>4</td><td>5</td><td>5</td><td></td><td>5</td></tr>
<tr><th>9</th><td>2</td><td>3</td><td>4</td><td>3</td><td>1</td><td>3</td><td>5</td><td>5</td><td>5</td><td></td></tr>
</tbody>
</table>
Fig. 3