Mathematics — Graph Theory · gallai-edge-colorings
Problem
Let n be a positive integer. Let E be the edge set of the complete graph Kn. A map f:E→Z is said to be an edge-coloring of Kn. The values of this map f are called the colors of the edge-coloring f. (We imagine each value f(e) to be a color assigned to the edge e.)
An edge-coloring f:E→Z of Kn is said to be Gallai if for any three distinct vertices i,j,k, at least two of the three numbers f(ij), f(jk) and f(ki) are equal (where we use the shorthand uv for the edge {u,v}, as usual). (Visually speaking, this means that each triangle has at least two equally-colored sides.)
Prove that the maximum number of colors (i.e., the maximum size of f(E)) in a Gallai edge-coloring f of Kn is n−1.