The answer is $2n^2$. Construction: Pick a $ K_{2n+1} $ without a matching of $n$ edges. It's easy to see that it works. Bound: We do this by induction on $n$. We claim that there must be a vertex $v$ of degree at least $2n$. If not, then pick the coloring with the least number of monochromatic edges. If a vertex $v$ belongs to at least $2$ such edges, among its neighbors there is a color appearing at most once and we can recolor $v$ with that color and the number of monochromatic edges decreases, contradicting the minimality of the coloring. Let $v$ be a vertex of degree at least $2n$ and let $G'$ be the induced subgraph without $v$. Then there must be a vertex $v'$ with degree at least $ 2n-2 $ in $G'$ (else we can apply the above claim for $n-1$ colors and color $v$ with the $n$-th color). Color $v$ and $v'$ with color $n$ and apply the inductive hypothesis for $G'$ without $v'$. Since $v$ and $v'$ contribute to at least $ 2n+2n-2=4n-2 $ edges, we get a total of at least $ 2(n-1)^2+4n-2=2n^2 $ edges.

The answer is $2n^2$. Construction: Pick a $ K_{2n+1} $ without a matching of $n$ edges. It's easy to see that it works. Bound: We do this by induction on $n$. First of all, notice that any vertex of degree less than $n$ does not affect us, since if we color all other vertices, there will be a color which doesn't appear among its neighbors and we can color it with that missing color. So assume that all vertices have degree at least $n$. We claim that there must be a vertex $v$ of degree at least $2n$. If not, then pick the coloring with the least number of monochromatic edges. If a vertex $v$ belongs to at least $2$ such edges, among its neighbors there is a color appearing at most once and we can recolor $v$ with that color and the number of monochromatic edges decreases, contradicting the minimality of the coloring. Let $v$ be a vertex of degree at least $2n$. We have two cases: Case 1. $v$ is a universal vertex (that is, $v$ is adjacent with every other vertex). Let $G'$ be the induced subgraph without $v$. Then there must be a vertex $v'$ with degree at least $ 2n-2 $ in $G'$ (else we can apply the above claim for $n-1$ colors and color $v$ with the $n$-th color). Then color $v$ and $v'$ with color $n$ and apply the inductive hypothesis for $G'$ without $v'$. Since $v$ and $v'$ contribute to at least $ 2n+2n-2=4n-2 $ edges, we get a total of at least $ 2(n-1)^2+4n-2=2n^2 $ edges. Case 2. $v$ is not a universal vertex. Let $v'$ be a vertex which is not adjacent to $v$. If $v'$ has degree at least $2n$, color $v$ and $v'$ with color $n$ and apply the inductive hypothesis for the other vertices. Again, since $v$ and $v'$ contribute to at least $4n$ edges, we get a total of more than $ 2n^2 $ edges. If $v'$ has degree less than $2n$, there is a vertex $u$ which is adjacent to $v$ but not to $v'$. Color $ v,v',u $ with color $n$ and apply the inductive hypothesis. By the beginning remark, $v'$ and $u$ have degree at least $n$, so $ v,v',u $ contribute to at least $ 4n-1 $ edges, giving a total of more than $ 2n^2 $ edges.