Hint: The maximal $K_{r+1}$-free graph happens to be $r$-colorable.
More on the hint: Turán's theorem bounds the number of edges that a $K_{r+1}$-free graph can have. The tight example is $r$-colorable. Since $K_{r+1}$ isn't $r$-colorable, Turán's theorem answers your question.
Another way to solve this uses David's method. Let $n_1,\ldots,n_r$ be the sizes of the color classes. We can assume that all edges connecting different color classes are there. The only edges not there are the within-class edges, which number
$$ \binom{n_1}{2} + \cdots + \binom{n_r}{2} = \frac{n_1^2 + \cdots + n_r^2}{2} - \frac{n}{2}. $$
Since $n$ is constant, we might as well minimize $n_1^2 + \cdots + n_r^2$. Consider any two $n_1,n_2$ satisfying $n_2 - n_1 \geq 2$. If we increase $n_1$ by one and decrease $n_2$ by one then the new sum of squares is
$$ (n_1+1)^2 + (n_2-1)^2 = n_1^2 + n_2^2 + 2(n_1 - n_2 + 1) < n_1^2 + n_2^2. $$
This shows that the optimum is achieved for a setting in which $|n_i - n_j| \leq 1$ for all $i,j$. Thus for some $m$ and $k$, wlog
$$n_1 = \cdots = n_k = m+1, \, n_{k+1} = \cdots = n_r = m.$$
Since the total number of vertices is $n$, we must have
$$ n = k(m+1) + (r-k)m = rm + k. $$
We can assume that $0 \leq k < r$ (i.e. $n_r = m$), hence $k = n \mod{r}$ and $m = \lfloor n/r \rfloor$.
