Team Selection Test for IMO

The problem can be reformulated in terms of graph theory: Let $G$ be a connected graph with $n$ vertices. If the degree of each vertex is at least $k$, then the edges of $G$ can be colored into $n-k$ colors so that for any pair of vertices there is a path between them not containing identically colored edges. We will prove the following slightly stronger statement: Let $G$ be a connected graph with $n$ vertices and $\alpha(G)$ be the minimal degree and $K$ be any clique of $G$ consisting of vertices with minimal degree. The edges of $G$ can be colored into $n-\alpha(G)$ colors so that the clique $K$ is colored into a single color and for any pair of vertices there is a path between them not containing identically colored edges. The statement will be proved at fixed $\alpha(G)$ by induction over $n$.

If $\alpha(G) = 1$, then we take any spanning tree of $G$ having $n-1$ edges and color it obviously by $n-1$ colors.

Induction base: Since $n > \alpha(G)$ we start with $n = \alpha(G)+1$. Then $G$ is a complete graph and we can color all vertices in one color.

Now suppose that $1 < \alpha(G) < n-1$. Let $K$ be a maximal clique consisting of only vertices having degree $\alpha(G)$ and put $l = |K|$. Note that if $l = \alpha(G)+1$ then since $G$ is connected we get $K = G$, so $G$ is complete and one color is sufficient. Suppose $1 \le l \le \alpha(G)$. Let $G_1, \dots, G_p$ be connected components of $G-K$ and $K_i$ be the vertices directly connected to some vertex in $G_i$, $i = 1, \dots, p$. Without loss of generality suppose that $|K_1| \ge |K_i|$ for $i = 2, \dots, p$. Let $f(G)$ be the minimal number of colors necessary for proper coloring of $G$. By inductive hypothesis $f(G_i) \le n_i - \alpha(G_i)$, where $n_i = |G_i|$.

Case 1. $1 = |K_1| = 1 < |K|$. By contracting $K$ into single vertex, we get a graph $G'$. Note that $|G'| = n-l+1$ and $\alpha(G') \ge \alpha(G)$ ($\alpha(G') = \alpha(G)$ if there is a vertex in some $G_i$ with degree $\alpha(G)$ or each vertex in $K$ is connected to exactly one vertex in $G-K$). Therefore, by inductive hypothesis, $f(G') \le n-l+1-\alpha(G)$. Now for proper coloring of $G$ we take a coloring of $G'$ and color all edges of $K$ by some new color, spending in total less or equal than $n-l+1-\alpha(G)+1 \le n-\alpha(G)$ colors, since in our case $l = |K| > |K_1| = 1$.

Case 2. $1 < |K_1| = l_1 < |K|$. By contracting $K_1$ into single vertex $v$ $G$ transfers into $G'$ and $K$ transfers into $K'$. Note that $|G'| = n - l_1 + 1$ and $\alpha(G') = \alpha(G) - l_1 + 1$. By inductive hypothesis, there is a proper coloring of $G'$ by $f(G') \le n - \alpha(G)$ colors where all edges of $K'$ are colored by a single color $c$. Now for proper coloring of $G$ we take a coloring of $G'$ and color all remaining edges with both vertices in $K$ in $c$ and with one edge in $K$ with the color of the edge from $v$ to other endpoint, spending in total less or equal than $n - \alpha(G)$ colors.

Case 3. $K_1 = K$. By inductive hypothesis, $f(G') \le n_i - \alpha(G_i)$. Since $K$ is maximal, $\alpha(G_i) \ge \alpha(G) - l + 1$. We can color all edges of $K$ and all edges from $K$ to $G_1$ by some color and edges from $K$ to $G_i, i = 2, \dots, p$ by new distinct colors. Then
$$f(G) \le t+0+\sum_{i=1}^{p}(n_i-\alpha(G_i)) \le t+\sum_{i=1}^{p}(n_i-\alpha(G)+l-1) = n-\alpha(G)+(p-1)(l-\alpha(G)) \le n-\alpha(G).$$