A Bulgarian Winter Competition, 2020. Part III

It’s the third post about that competition. In the previous two, the problems #4 given at the grades 11 and 12 were considered. Here is the fourth problem of the grade 10.

Problem 10.4. Let $K_n$ be a complete graph with $n$ vertices (every two vertices are connected), which edges are colored. We say the edges of $K_n$ are regularly colored if the edges of any triangle are either of the same color or of distinct colors.
a) Prove that in any regularly colored $K_n$ the number of used colors is at least $\sqrt{n}+1$ providing at least two colors present.
b) Does there exists a regular coloring of $K_{25}$ using exactly $6$ colors?

Solution

Part a) Assume on the contrary, the colors are at most $\sqrt{n}$ . Take some vertex $v_0$ . Among all edges incident with it, there are at least $m:=\left\lceil (n-1)/\sqrt{n}\,\right\rceil$ edges of the same color, say white. The set $S$ of the vertices, $v_0$ is connected to along these edges, plus $v_0$ comprises a clique. Indeed, if for some $u,v\in S$ the color of $uv$ is not white, it would contradict to the requirement. Let $S'$ be the maximal clique containing $S\cup\{v_0\}$ . Take a vertex $v_1\notin S'$ . Such one does exist, otherwise there would be only one color used. Two observations.

There is no white edge among the edges $\{v_1 u, u\in S'\}$ . Indeed suppose some $v_1u_0,u_0\in S'$ is white. Then all $\{v_1 u, u\in S'\}$ are also white, since $u_0u$ is white. A contradiction with the maximality of $S'$ .
All edges $v_1 u, u\in S'$ must be of distinct colors. Indeed if there are two ones of the same color, that color should be white, a contradiction with the first observation.

By the second observation there are at least $|S'|\geq m+1$ distinct colors. To recap, we assumed there are at most $\sqrt{n}$ colors and established there are at least $m+1=\left\lceil (n-1)/\sqrt{n}\,\right\rceil+1$ ones. To get a contradiction it’s enough to establish

$\sqrt{n} < \left\lceil (n-1)/\sqrt{n}\,\right\rceil+1$

But it’s easily checked that even $\sqrt{n} < (n-1)/\sqrt{n}+1$ . $\blacksquare$

Part b) We prove for any prime $p$ , the edges of $K_{p^2}$ can be colored with $p+1$ colors as desired. I borrow the solution given in [1], this is also the official solution.
Let the pairs $(i,j), i,j\in \{0,1,\dots,p-1\}$ be the vertices of $K_{p^2}$ and the colors be $\{0,1,\dots,p-1,p\}$ . For any two vertices $u=(i_1,j_1), v=(i_2,j_2)$ we color $u\,v$ with the color $(j_2-j_1)/(i_2-i_1)$ (the operation taken in the field $\mathbb{Z}/p\mathbb{Z}$ , see the remark below) in case $i_2-i_1\neq 0$ and with color $p$ in case $i_1=i_2$ . $\blacksquare$

Remark. For any $a,b\in \mathbb{Z}/p\mathbb{Z}, b\neq 0$ where $p$ is a prime, there is unique $x\in \mathbb{Z}/p\mathbb{Z}$ with $bx=a$ . Thus, we can define $a/b\in \mathbb{Z}/p\mathbb{Z}$ . One may interpret the vertex $(i,j)$ geometrically as a point on the plane with $i,j$ as its $xy$ coordinates. Then the color of a segment $AB, A(i_1,j_1), B(i_2,j_2)$ is associated with its slope $(j_2-j_1)/(i_2-i_1)$ . In case $i_1=i_2$ one could define the slope being $\infty$ . For a “triangle” $ABC$ , if two of its sides have the same slopes, the third one is also the same. This means the coloring is regular.