Problem

Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 10.8

Tags: combinatorics, graphs, Coloring



Consider a complete graph on $4046$ nodes, whose edges are colored in some colors. Let's call this graph $k$-good if we can split all its nodes into $2023$ pairs so that there are exactly $k$ distinct colors among the colors of $2023$ edges that connect the nodes from the same pairs. Is it possible that the graph is $999$-good and $1001$-good but not $1000$-good? Proposed by Anton Trygub