Problem

Source: X International Festival of Young Mathematicians Sozopol 2019, Theme for 10-12 grade

Tags: combinatorics, graph, graph theory



Let $G$ be a bipartite graph in which the greatest degree of a vertex is 2019. Let $m$ be the least natural number for which we can color the edges of $G$ in $m$ colors so that each two edges with a common vertex from $G$ are in different colors. Show that $m$ doesn’t depend on $G$ and find its value.