Any solution??

This is the official solution: The problem can be reformulated in term 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\leq l \leq \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| \geq |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) \leq 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') \geq \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')\leq 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 \leq 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')\leq 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 box 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')\leq n_i - \alpha(G_i)$. Since $K$ is maximal, $\alpha(G_i) \geq \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)\leq t + 0 + \sum\limits_{i=1}^p(n_i-\alpha(G_i)) \leq t + \sum\limits_{i=1}^p(n_i-\alpha(G) + l -1)\] \[= n- \alpha(G) + (p-1)(l-\alpha(G)) \leq n - \alpha(G)\] The proof is completed.

In case 2 there is a problem, since the new vertex of $K'$ may have a larger degree than the other ones.I think case 1 is flawed as well.

math90 wrote: In case 2 there is a problem, since the new vertex of $K'$ may have a larger degree than the other ones... I think, the real intention here was to define $K$ as "the maximal clique consisting of vertices with [at least] minimal degree" or shortly "the maximal clique". I tried to do the same inductive approach, not with cliques but removing only an vertex. I was short of just one color to the right result. Note that the maximal clique has at least $2$ vertices. Look at the third case, it's instructive, this one $$\alpha(G_i) \geq \alpha(G)-\ell+1$$Assume $\ell=2$. So, you "remove" $2$ vertices and the minimum degree of every component decreases at most by $1$ (not by $2$). This is the key. Because if you remove just a vertex, you cannot expect the maximum degree of the components to stay the same. So, remove $2$ vertices and gain one degree simply because you took the maximal clique!!