Problem 1996

$c = \frac{k(kn - n + 2)}{2(kn + 1)}$.

First, we prove $c \ge \frac{k(kn - n + 2)}{2(kn + 1)}$. Consider a complete graph $K_{kn+1}$ with any $n$-colouring of the vertices. Suppose that the numbers of vertices coloured by 1, 2, ..., $n$ are $a_1, a_2, ..., a_n$, respectively. Then
$$\begin{aligned} a_1^2 + a_2^2 + \dots + a_n^2 &\ge \frac{(a_1 + a_2 + \dots + a_n)^2}{n} \\ &= \frac{(kn + 1)^2}{n} \\ &= k^2n + 2k + \frac{1}{n}. \end{aligned}$$
As $a_1, a_2, ..., a_n$ are integers,
$$a_1^2 + a_2^2 + \dots + a_n^2 \ge k^2n + 2k + 1.$$
Therefore, the number of mono edges is:
$$\begin{aligned} \sum_{i=1}^{n} C_{a_i}^2 &= \frac{1}{2} \left( \sum_{i=1}^{n} a_i^2 - \sum_{i=1}^{n} a_i \right) \\ &\ge \frac{1}{2} (k^2n + 2k + 1 - (kn + 1)) \\ &= \frac{1}{2} k(kn - n + 2), \end{aligned}$$
which implies $c \ge \frac{k(kn - n + 2)}{2(kn + 1)}$.

Next, we give three proofs that $c = \frac{k(kn - n + 2)}{2(kn + 1)}$ satisfies the problem assertion.

Proof 1

For any $kn$-regular graph $G$, it is well known that $G$ has a $(kn+1)$-colouring such that adjacent vertices are of different colours. Divide the $kn+1$ colours randomly into $n$ groups such that one group contains $k+1$ colours while each of the others contains $k$ colours, and for all these divisions, they have equal probabilities. Now change all colours of a group into one colour. For any edge of $G$, initially, it is incident to vertices of different colours; after changing the colours, it is incident to vertices of the same colour, namely, it becomes a mono edge with a probability
$$\frac{C_{k+1}^2 + (n-1)C_k^2}{C_{kn+1}^2} = \frac{k(k+1) + k(k-1)(n-1)}{(kn+1)(kn)} = \frac{kn - n + 2}{n(kn+1)}.$$
Therefore, after changing the colours, the expected number of mono edges is
$$\frac{kn - n + 2}{n(kn + 1)} \cdot \frac{knm}{2} = m \cdot \frac{k(kn - n + 2)}{2(kn + 1)} = cm.$$
There must exist an $n$-colouring of $G$ such that the number of mono edges is less than or equal to $cm$. This verifies the problem assertion.

Proof 2

Suppose that among all $n$-colourings of $G$, the minimum number of mono edges is $T(G)$. Let $V$ consist of vertices of $G$. For a permutation $\pi = (v_1, v_2, . . . , v_m)$ of $V$, colour $v_1, v_2, . . . , v_m$ in order (by one of $n$ colours) as follows. For a vertex $v$, suppose that in $\pi$, $A_{\pi}(v)$ of $kn$ neighbouring vertices of $v$ appear before $v$. We colour $v$ with the colour that appears least frequently among those $A_{\pi}(v)$ neighbours (it appears at most $\lfloor A_{\pi}(v)/n \rfloor$ times). According to this greedy algorithm, it is guaranteed that
$$T(G) \leq F(\pi) := \sum_{v \in V} \left\lfloor \frac{A_{\pi}(v)}{n} \right\rfloor.$$
The above inequality holds for any permutation $\pi$. It suffices to prove, for all $m!$ permutations, the average of $F(\pi)$ is $\frac{k(kn - n + 2)}{2(kn + 1)} \cdot m$, so that some permutation $\pi$ gives a desired $n$-colouring. For a vertex $v$, let its neighbours be $\{u_1, u_2, \dots, u_{kn}\}$. Consider $B = \{v, u_1, u_2, \dots, u_{kn}\}$: among the $m!$ relative orders of elements of $B$ given by all $m!$ permutations, $v$ appears at position 1, 2, $\dots$, $kn + 1$ with equal probability $\frac{1}{kn + 1}$. Hence, as $\pi$ traverses all $m!$ permutations, the average of $\left\lfloor \frac{A_{\pi}(v)}{n} \right\rfloor$ is
$$\begin{aligned} \frac{1}{kn+1} \sum_{a=0}^{kn} \left\lfloor \frac{a}{n} \right\rfloor &= \frac{1}{kn+1} (0 \times n + 1 \times n + \dots + (k-1) \times n + k) \\ &= \frac{k(kn - n + 2)}{2(kn + 1)}. \end{aligned}$$
As a result, the average of $F(\pi)$ is $\frac{k(kn - n + 2)}{2(kn + 1)} \cdot m = cm$.

Proof 3

For a $kn$-regular graph $G$, let $A = |V(G)|$ be the number of vertices of $G$. Since there are only finitely many $n$-colourings of $G$, there must be one with the minimum number of mono edges, say $C$. We have the following claims on $C$.

Claim 1 For every vertex $v$, $v$ has at most $k$ neighbours that are in the same colour as $v$; if this does occur, then $v$ has exactly $k$ neighbours in each of the $n$ colours (we call this $v$ a "balanced vertex").

Proof of claim 1 Let $v$ be of colour $P$. If there is another colour $Q$ such that among $v$'s neighbours, the number of vertices in colour $P$ is larger than that in colour $Q$, then we change the colour of $v$ from $P$ to $Q$. This will reduce the number of mono edges, which is a contradiction. Hence, there are fewest neighbours of $v$ in colour $P$ (or one of the fewest); as $v$ has $kn$ neighbours, the claim is verified.

Claim 2 Adjacent balanced vertices must be monochromatic.

Proof of claim 2 Let $v, w$ be adjacent balanced vertices, $v$ in colour $P$ while $w$ in colour $Q$. Changing $v$ to $Q$ and $w$ to $P$, $vw$ will not be a mono edge, but the numbers of mono edges incident to $v$ or $w$ will each decrease by 1, a contradiction.

Claim 3 If $v$ is not a balanced vertex, $v$ is adjacent to $r$ balanced vertices which have different colours from $v$, then there are at most $k - \frac{r}{k+1}$ mono edges incident to $v$.

Proof of claim 3 Consider the edges between these $r$ balanced vertices. As each balanced vertex is adjacent to at most $k$ balanced vertices of its colour, in the subgraph of these vertices, the degree of each vertex does not exceed $k$. Now we can choose at least $\frac{r}{k+1}$ of these balanced vertices such that any two of them are not adjacent (assume that at most $t$ vertices can be chosen, then they have $tk$ or fewer neighbours, $tk+t \ge r$, or $t \ge \frac{r}{k+1}$). Change them to the colour of $v$. From the properties of balanced vertices, we see that the number of mono edges does not change; however, if the number of mono edges emanating from $v$ exceeds $k$, then changing $v$'s colour will reduce the number of mono edges, a contradiction. Therefore, the number of mono edges emanating from $v$ does not exceed $k$, and hence there are at most $k - \frac{r}{k+1}$ mono edges incident to $v$.

Let $a$ be the number of balanced vertices in $G$. There are two situations.

(i) If $a \le \frac{k+1}{kn+1}A$. By calculating the number of mono edges emanating from each vertex in two ways, we find that the total number of mono edges does not exceed
$$\begin{align*} \frac{1}{2}(ak + (A-a)(k-1)) &= \frac{1}{2}((k-1)A + a) \\ &\le \frac{1}{2} \left( (k-1)A + \frac{k+1}{kn+1}A \right) \\ &= \frac{k(kn-n+2)}{2(kn+1)}A. \end{align*}$$

(ii) If $a > \frac{k+1}{kn+1}A$. From Claim 2, it follows that the heterochromatic neighbours of a balanced vertex are never balanced vertices. Thus, the number of edges connecting a balanced vertex and a heterochromatic neighbour is $ak(n-1) > \frac{k(k+1)(n-1)}{kn+1}A$. Now for each non-balanced vertex, consider its heterochromatic balanced (vertex) neighbours: let the numbers be $r_1, r_2, \dots, r_{A-a}$. We have
$$r_1 + r_2 + \dots + r_{A-a} > \frac{k(k+1)(n-1)}{kn+1} A.$$
From Claim 3, the number of mono edges does not exceed
$$\begin{align*} \frac{1}{2} \left( ka + \sum_{i=1}^{A-a} \left( k - \frac{r_i}{k+1} \right) \right) &= \frac{1}{2} \left( kA - \frac{1}{k+1} \sum_{i=1}^{n-a} r_i \right) \\ &< \frac{1}{2} \left( kA - \frac{k(k+1)(n-1)}{(k+1)(kn+1)} A \right) \\ &= \frac{k(kn-n+2)}{2(kn+1)} A. \end{align*}$$
Therefore, $c = \frac{k(kn - n + 2)}{2(kn + 1)}$ as desired.