Let $T = (V, E)$ be a tree. Let $\Sigma$ be a finite set of labels. Given a label function $\ell : V \to \Sigma$, the cost of $\ell$ is given by


$$\mu(\ell) = \left| \{(u,v) \in E \mid \ell(u) \neq \ell(v) \} \right|$$


i.e., $\mu(\ell)$ is the number of edges whose vertices have different labels. Given the labels of all leaves of $T$, I would like to find a labeling for internal vertices with the minimum cost $\mu(\ell)$.


I have no idea to solve it. Does anyone have any idea? Thank you in advance! 



How to label a tree with minimum cost?
**Notation** Given a tree $T$, let $V(T)$ be the set of its vertices, let $L(T)\subseteq V(T)$ be the set of its leaves. Denote by $T'=T\setminus L(T)$, i.e. let it be the subtree obtained from $T$ removing its leaves. For every $v\in T'$ let $L\_v(T)\subseteq L(T)$ be the set of leaves (of $T$) adjacent to $v$.


**The idea** is the following: let $T$ be a tree with a partial labelling $\ell: L(T)\to\Sigma$ and let $v\in L(T')$. Now, consider the restriction of $\ell$ to $L\_v(T)$ and suppose that there is a color $\sigma\in\Sigma$ that appears strictly more often than the others as a value of $\ell|\_{L\_v(T)}$. Then, a right thing to do (to minimize the cost of a final coloring) is to set the color of $v$ to $\sigma$. 
Indeed, if you consider any coloring $\ell\_1:V(T)\to\Sigma$ that extends $\ell$, you might consider an alternative coloring $ \ell\_2:V(T)\to\Sigma$ that satisfies $\ell\_2(v)=\sigma$ and agrees with $\ell\_1$ on $V(T)\setminus\{v\}$. Notice that necessarily $\mu(\ell\_2)\leq\mu(\ell\_1)$. (a key point here is that we chose $v$ to be a leaf of $T'$)


Now, we are ready for an answer (I am not claiming this is the most efficient implementation, but it doesn't look too bad).


**Preparation**. Let $S=\mathcal P(\Sigma)\setminus\{\emptyset\}$ the collection of nonempty subsets of $\Sigma$. Let $T$ be a tree with a partial labelling $\ell: L(T)\to\Sigma$. We associate to it the partial multilabelling $\bar\ell: L(T)\to S$ given by $\bar\ell(v)=\{\ell(v)\}$.


**The algorithm**. Let $T$ be a tree with a partial multilabelling $\bar\ell:L(T)\to S$. If $V(T)= L(T)$, end; otherwise, let $v\in L(T')$. For every $\sigma\in\Sigma$ count $n\_v(\sigma):=\#\{w\in L\_v(T):\ \sigma\in\bar\ell(w) \}$. Let $\Sigma\_v = \operatorname{argmax} (n\_v) \in S$ (that is, let $n(v) = \max\{n\_v(\sigma):\ \sigma\in\Sigma\}$ and let $\Sigma\_v:=\{\sigma\in\Sigma:\ n\_v(\sigma) = n(v) \}$. 


Now, consider the subtree $\hat T =T\setminus L\_v(T)$. Notice that $L(\hat T)=\{v\}\cup L(T)\setminus L\_v(T)$. Consider the partial multilabelling $\hat\ell:L(\hat T)\to S$ that agrees with $\bar\ell$ on $L(T)\setminus L\_v(T)$ and satisfies $\hat \ell(v)=\Sigma\_v$. Iterate on $(\hat T,\hat\ell)$.


At the end, we have a tree $\tilde T$ that satisfies $V(\tilde T)=L(\tilde T)$. This happens only if $V(\tilde T)=\{v\}$ or $V(\tilde T)=\{v\_1,v\_2\}$. In the first case, we choose any labelling $\ell:V(\tilde T)\to\Sigma$ that satisfies $\ell(v)\in\bar\ell(v)$. In the second case, we choose $\ell:V(\tilde T)\to\Sigma$ so that $\ell(v\_i)\in\bar\ell(v\_i)$ for $i=1,2$, and we also make sure that $\ell(v\_1)=\ell(v\_2)$ in case $\bar\ell(v\_1)\cap\bar\ell(v\_2)\neq \emptyset$.


Returning backwards, we have a labelling $\ell:V(\hat T)\to\Sigma$ that minimizes the cost subject to the boundary multilabelling. For every $w\in L\_v(T)$ we define $\ell(w)=\ell(v)$ in case $\ell(v)\in\bar\ell(w)$, otherwise we choose arbitrarily $\ell(w)\in\bar\ell(w)$. This defines an extension of the labelling to $V(T)$ that minimizes the cost, subject to the boundary multilabelling. 


Repeat until you get back to your original tree.


