Minimum number of links connecting two nodes of the same color Preliminaries
Consider an undirected network of $N$ nodes ($V$ is the set of nodes), described by the symmetric adjacency matrix $A = \{a_{v,w}\} \in \{0,1\}^{N \times N}$ without self-loops (i.e. $a_{v,w} = 1$ if $v$ and $w$ are connected, and $0$ otherwise; moreover, $a_{v,v} = 0 ~\forall v \in V$).
Suppose that for each node, there exists a path towards any other node (the graph is connected).
Now, consider a coloring $\alpha \in K^N$, where $K$ is the set of colors ($|K| \geq 2$), such that for any node $v$ there exists another node $w$ connected to $v$ (i.e. $a_{v,w}=1$ ) with the same color of $v$ (i.e. $\alpha_w = \alpha_v$).
Let's introduce the set
$$B(\alpha) = \left\{\beta \in K^N : \beta_v \neq \alpha_v ~\forall \in V\right\}.$$
In other words, $B(\alpha)$ contains all the colorings such
that all nodes have different color with respect to $\alpha$.
The problem
I'm looking for the solutions of this maximization problem:
$$M(\alpha) = \max_{\beta \in B(\alpha)} \sum_{v\in V}\left(\sum_{\substack{w \in V  \\ \alpha_w = \alpha_v}}a_{v,w} - \sum_{\substack{w \in V  \\ \beta_w = \beta_v}}a_{v,w}\right).$$
My question
This problem can be numerically solved by rewriting it in a integer-programming fashion. Anyway, I'd like to know if this problem has been already studied, and there are some results on the value of $M(\alpha)$  (i.e. upper and lower bounds).
Numerically (i.e. by checking this value for several randomly generated networks), it seems that:
$$M(\alpha) \leq N.$$
Alternative version of the problem
As it has been highlighted by Misha Lavrov, the problem can be stated as follows:
Find
$$m(\alpha) = \min_{\beta \in B(\alpha)} \sum_{v\in V}\sum_{\substack{w \in V  \\ \beta_w = \beta_v}}a_{v,w},$$
i.e. find the coloring $\beta$ such that it guarantees the minimum number of connections among nodes of the same colors. My claim is that:
$$m(\alpha) \geq \sum_{v\in V}\sum_{\substack{w \in V  \\ \alpha_w = \alpha_v}}a_{v,w} - N,$$
since
$$M(\alpha) = \sum_{v\in V}\sum_{\substack{w \in V  \\ \alpha_w = \alpha_v}}a_{v,w} - m(\alpha).$$
 A: I think that the bound is not working, For example taking the following adjency matrix, the fixed coloring (with $K=\{0,1,2\}$): \begin{align}
A = \begin{pmatrix}
0 & 1 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 0 & 0 & 1\\
1 & 1 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 1\\
0 & 1 & 0 & 0 & 0 & 1 & 0
\end{pmatrix}, \quad \alpha = \begin{pmatrix}
0\\
0\\
0\\
1\\
1\\
2\\
2
\end{pmatrix}, \quad \beta = \begin{pmatrix}
1\\
1\\
2\\
0\\
2\\
1\\
0
\end{pmatrix}
\end{align}
As you can see $f(\alpha) = 10$ and $f(\beta) = 2 < 10 - 7  = f(\alpha) - N$.
A: Let $k = |K|$, and $f(\chi)$ be the number of edges whose two endpoints have the same color in coloring $\chi$.
If $k = 2$, the gap is always $0$, i.e., $f(\alpha)$ is always equal to $f(\beta)$.
If $k > 2$, the gap can in fact be as high as $\Theta(N^2/k^2 - k)$. In fact, let the graph consist of $k$ (almost) equal-sized bipartite graphs (with $k$ more edges to make it connected). Here each bipartite has (almost) equal number of nodes on each side and full connection in-between. Let $\alpha$ color each bipartite graph a different color. We have $f(\alpha) = \Theta(N^2/k^2)$. We can in fact choose $\beta$ such that $f(\beta) = O(k)$ (here we use the property that $k > 2$). Hence the gap.
