Let $ K_n$ be a graph with $ n$ vertices and $ d_i = n - 1$ for each vertice($ d_i$ denotes the degree). we want to color the edges of this graph using $ r \ge 2$ colors with this property: $ i)$ At least two colours are used. $ ii)$ any three vertices of the polygon determine either three segments of the same colour or of three different colours. we'll prove $ r \ge \sqrt {n} + 1$. let's suppose $ r < \sqrt {n} + 1$.then consider a vertice $ a$. $ a$ has $ n - 1$ neighbors and there exists a color that is used in a number bigger than $ \sqrt {n} - 1$ in the edges connecting this vertice to other vertices.suppose that this color is $ c_1$ and the set of vertices connected to $ a$ with an edge of this color be $ S$. obviously all edges between the vertices of $ S$ is $ c_1$. it's known that there exists at least one vertice ,let's call it $ b$, which is connected to $ a$ with a different color than $ c_1$, say $ c_2$.but one can easily see that all edges between the vertice $ b$ and the set $ S$ are mutually colored differently and also different from $ c_1$ and $ c_2$.so it directly implies that $ r > 2 + \sqrt {n} - 1 = \sqrt {n} + 1$. so we have a clear contradiction. for the next part we choose $ n$ s.t. it is a perfect square. then $ \sqrt {n} + 1$ color $ = \{c_1,...,c_{\sqrt {n} + 1}\}$ are chosen and used in this way: take a vertice $ a$ and connect it with other vertices by using each color exactly $ \sqrt {n} - 1$ times. the color of other edges are defined uniquely.

Could you clarify the last bit? I don't think it is correct.

i wasn't thinking right when i said that the other edges will be defined uniquely!sorry ! i saw this problem a long time ago in a book.but the question didn't have the second part. at first, it's obvious that if the equality occurs then $ n$ is a perfect square. since for each color we can't choose a vertice and color more than $ \sqrt{n}-1$ of the edges connected to it by one color and also because of having $ \sqrt{n}+1$ colors and $ (\sqrt{n}-1).(\sqrt{n}+1)=n-1$ we must use $ \sqrt{n}-1$ times each color for each vertice. so the reason for which i said that we must color the edges in that way(in my previous post) was this. but i can't prove that what i said is correct(i think it must be so!),though i 've found how to color edges for $ n=4,9$. anyway,any proof for this part should go by this way. sorry again !

I proposed this problem, but I do not know all cases in which equality occurs (if anybody does, please let me know). But I'm sure that equality will occur if $ n - 1$ is... prime. Or a prime power. Try to prove that.

I'll quote gjw from the forum of the Austrian Mathematical Olympiad. Quote: Das ist doch ein altes, wohlbekanntes Beispiel... Es wurde bereits in den 1980er Jahren in Bulgarien bei einem Wettbewerb verwendet. Vollstaendig analysiert wurde es dann 1994 von Coburn Ward und Sándor Szabó, unter dem Namen "swell-colorings of complete graphs": On swell-colored complete graphs. Acta Mathematica Universitatis Comenianae 63 (1994), 303--308. Ward und Szabó zeigen unter anderem, dass Gleicheit genau dann gilt, wenn es eine endliche affine Ebene der Ordnung n-1 gibt. Fuer die MEMO-Version reichen natuerlich die Primzahlfaelle aus. Translation: That's an old, well-known problem... It has been used already in 1980 in Bulgaria for a competition. In 1994, the problem has been fully analysed of Coburn Ward and Sándor Szabó, with the name "swell-colorings of complete graphs": On swell colored complete graphs. Acta Mathematica Universitatis Comenianae 63 (1994), 303--308. Ward and Szabó showed among others that equality is attained if and only if there exists a finite affine plane of order n-1. For the MEMO, the cases where n-1 is prime, are of course sufficient.

Hi, I have tried to solve this problem (equality part), and I couldn't prove that for $ n-1$ prime, equality holds. Can anyone help me?

step (1) is obvious so i will prove the second step. let$p$ be any prime .suppose $X=\left \{ (x,y)\mid x,y\in \mathbb{N},1\leq x,y\leq p \right \}$ in the plane. If the line which pass from the points $A=(x_{1},y_{1}),B=(x_{2},y_{2})$ ( these points are in $X$ )is not parallel by $O_{x}$ we will color the edge between $A,B$ by $\cot _{p}\widehat{BAOx}$ (The line $AO_{x}$ is parallel to $x$exists).(and we defined $\cot _{p}\widehat{CDE}=\cot \widehat{CDE}(mod p)$. if the line $AB$ is parallel to $O_{x}$ we put color of the edge between $A,B$ by $p+1$.