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^{\prime }$. Note that $|G^{\prime }|=n-l+1$ and $\alpha (G^{\prime })\ge \alpha (G)$ ($\alpha (G^{\prime })=\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^{\prime })\le n-l+1-\alpha (G)$. Now for proper coloring of $G$ we take a coloring of $G^{\prime }$ 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^{\prime }$ and $K$ transfers into $K^{\prime }$. Note that $|G^{\prime }|=n-l_1+1$ and $\alpha (G^{\prime })=\alpha (G)-l_1+1$. By inductive hypothesis, there is a proper coloring of $G^{\prime }$ by $f(G^{\prime })\le n-\alpha (G)$ colors where all edges of $K^{\prime }$ are colored by a single color $c$. Now for proper coloring of $G$ we take a coloring of $G^{\prime }$ 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^{\prime })\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).$$