Sorry if this is a stupid question, but if all of $n,k,m$ are odd, how can there exist a $kn$-regular graph with $m$ vertices? @below - Thanks, got it

@above I think the question is clear, since the precondition is JustPostChinaTST wrote: For any positive integer $m$ and a $kn$-regular graph $G$ with $m$ vertices, ... So indeed it suggests $m \ge kn+1$ and $knm$ is even.

BUMP!!!!!!!

Slightly troll. Here is a solution with cosinechicken, william122, and ewan: We claim the answer is \[ \frac{1}{nk+1} \left(\sum_{a=0}^{kn} \left\lfloor \frac an \right\rfloor \right) = \frac{k + n(1 + \cdots + (k-1))}{nk+1} = \frac{n\binom k2 + k}{nk+1}. \]Call that expression $r(n,k)$. We first show that $c \geq r$. Indeed, consider $G = K_{kn+1}$, with $a_1, \ldots, a_n$ vertices colored with each color. Then, there are $\sum \binom{a_i}2$ monochrome edges, and by convexity of $\binom\bullet 2$ we know that this is at least \[ (n-1) \binom k2 + \binom{k+1}2 = n\binom k2 + k \]indeed. This establishes $c\geq r$, and now we just need to show that $c\leq r$, i.e. for any such $G$ we can attain $\leq rm$ monochrome edges. To do this, consider such a $G$ and randomly permute its vertices from left to right. For each vertex $v$ let $s(v)$ denote the number of neighbors to its left. Then, by scanning greedily from left to right, we can always get at most $\left\lfloor \frac{s(v)}{n}\right\rfloor$ monochrome edges with right vertex $v$. Summing all monochrome edges by right vertex shows that we can always get atmost $\sum \left\lfloor \frac{s(v)}{n}\right\rfloor$ monochrome edges. So, by picking an appropriate permutation we can always do better than \[ \mathbb E\left[ \sum \left\lfloor \frac{s(v)}{n}\right\rfloor\right] = \sum_{a=0}^{kn} \mathbb E[|\{ v\colon s(v) = a\}|] \left\lfloor \frac a n \right\rfloor =\sum_{a=0}^{kn} \frac{m}{kn+1} \left\lfloor \frac a n \right\rfloor = rm \]indeed. Note: This proof is pretty similar to the probabilistic proof of Turan's theorem for independent sets.

this was stupid anyway the answer is $\frac{n\binom{k}{2}+k}{nk+1}$ and as noted above the full graph on $nk+1$ vertices if painted with $n$ colors has at least $n\binom{k}{2}+k$ monochromatic edges.As for the upper bound: the graph has $\frac{mkn}{2}$ edges and being $kn-$regular is at most $kn+1$-chromatic. So suppose we partition the vertices into $nk+1$ classes $A_1,A_2,A_3,...,A_{nk+1}$ and let $d_{ij}$ be the number of edges between $A_i$ and $A_j$ and $\sum_{i<j}d_{ij}=\frac{mkn}{2}$. Now we color each entire class $A_i$ with one of $n$ colors $c_1,c_2,...,c_n$ conditioned on that each color is used exactly $k$ times except $c_n$ that is used $k+1$ times. Now the probability that $A_i,A_j$ have the same color is precisely $P(A_i=A_j)=\sum_{k=1}^n P(Ai=c_k,A_j=c_k)=\sum_{k=1}^n P(A_i=c_k|A_j=c_k)P(A_j=c_k)= (n-1)\frac{k(k-1)}{(kn+1)kn}+\frac{(k+1)k}{(kn+1)kn}=\frac{nk(k-1)+2k}{(kn+1)kn}$ Therefore the expectation of monochromatic edges is $\mathbb{E} \left[ \sum \mathbb{I}_{[A_i=A_j]}d_{ij} \right]=\frac{nk(k-1)+2k}{(kn+1)kn}\sum d_{ij}=m\frac{n\binom{k}{2}+k}{nk+1}$