I'm assuming that by "vertex coloring" you are not referring to proper vertex coloring, since every proper vertex coloring has zero monochromatic edges.
I'll prove the claim using the Probabilistic method.
Given a graph $G=(V,E)$, and k colors, I'll define random coloring
as a function $C:V\to[k]$ (where $[k]:=\{1,2....,k\}$) as follow:
$$\forall v\in V, i\in[k]\ \ \ \ \mathbb {P}(c(v)=i)=\frac{1}{k}$$
Proposition
$$\forall e\in E\ \ \ \mathbb {P}(e\text{ is monochromatic})=\frac{1}{k}$$
The proposition implies the expected number of monochromatic edges for such random coloring is $\frac{\vert E\vert}{k}$.
Therefore, at least one random coloring induce no more then $\frac{\vert E\vert}{k}$ monochromatic edges, otherwise, the expectation value would be higher.
The proposition proof is quite simple:
$$\forall i\in [k],v,u\in V\ \ \ \ \mathbb P(c(u)=i\land c(v)=i) = \frac{1}{k^2}\implies\mathbb P(c(u)=c(v))=\frac{1}{k}$$
Where the last transition is true because there are k colors.