Here is a sketch of the official solution: Call a group of vertices $critical$ if it has $k$ vertices and exactly $5k+10$ edges. The main point is that if $G$ (the whole graph) isn't critical (if it is, note that $5000=5.998+10$), then we can add one edge so that again each group of $k$ vertices has max $5k+10$ edges. Now note that we want to add an edge between $x$ and $y$, such that $x, y$ don't belong both to a critical set. We present now the following $\textbf{Lemma}$: If two sets of vertices $A$ and $B$ are critical, then so is their union. $\textbf{Sketch of proof}$: If $f(X)$ is the number of edges in $X$, note that if $C$ is their intersection, then $f(D) \geq f(A)+f(B)-f(C) >... \geq 5|D|+10.$ (use $f(C)\leq 5|C|+10$ and $|D|=|A|+|B|-|C|$; $D$ is the union) $\blacksquare$ Now we take the union $A$ of all critical sets, which due to the lemma is a critical set. Take one vertex $x$ outside $A$ and $y$ in $A$, such that $xy$ isn't an edge, and we can add it ($x$ has $<5$ neighbors in $A$ due to the fact that we can't add it to $A$ - maximality of $A$, and obviously $A$ has more than $5$ vertices, because $k(k-1)/2>5k+10$).

Remark

Let $e(S)$ denote the number of edges in some set $S$, and call such a set $S$ saturated if $e(S)=5|S|+10$. The key claim is as follows. Claim: Suppose that the laws are all followed. Then union $S$ of saturated sets $S_1$ and $S_2$ is also saturated. Proof: We have the inequality $$e(S) \geq e(S_1)+e(S_2)-e(S_1 \cap S_2).$$This follows because the RHS counts every edge joining two vertices in either $S_1$ or $S_2$ exactly once, and every such edge clearly lies in $S$. On the other hand, because $S_1$ and $S_2$ are saturated, we have $e(S_1)+e(S_2)=5|S_1|+5|S_2|+20$, and because the laws are followed, $e(S_1 \cap S_2) \leq 5|S_1 \cap S_2|+10$, hence $e(S) \geq 5(|S_1|+|S_2|-|S_1 \cap S_2|)+10$, and the conclusion follows from inclusion-exclusion. This implies that every saturated set is the subset of some set $S$, at every point in time. If we have less than $5000$ edges then clearly $S$ isn't the whole graph, so take some vertex $v$ outside $S$ and connect it with a vertex $w$ in $S$. If this makes some set of vertices $T \ni v$ have more than $5|T|+10$ edges, then $T$ must have had at least $5|T|+10$ vertices before adding $\overline{vw}$, hence it was saturated. But $T \neq S$: contradiction. $\blacksquare$ Remark: Of course, this proof should work for any linear function.