This was also problem 2 of the Lithuanian Grand Duchy Olympiad 2023. The answer is 25.

Oh, that reminds my nostalgic memories. If I had solved it during the contest, my life would have been different. I hate this problem.

Answer: $25$. Example: Take $5$ subgraphs $A,B,C,D,E$. Let each of them has $5$ vertices and any two vertices in the same subgraph are not connected. Any two vertices in different subgraphs are connected. Proof: $\rule{15cm}{0.2mm}$ Claim: Everyone has at least $n-5$ friends. Proof: Let $A$ be a vertex. If $A$ is friend with all other vertices, then the claim is true. Let $B$ be a vertex which is not friend with $A$. There cannot be $4$ vertices which are not friend with both $A$ and $B$. So there are at least $n-5$ vertices which are friend with both $A$ and $B$. The claim is proven. $\rule{15cm}{0.2mm}$ $der \ v_i\geq n-5$ for all $i=1,2,...,n$ so $|E|=\frac{\sum{der \ v_i}}{2}\geq \frac{n^2-5n}{2}$ We don't have $6-$clique hence by Turan's Theorem, we have \[\frac{n^2-5n}{2}\leq |E|\leq \frac{4n^2}{10}=\frac{2n^2}{5}\iff 4n^2\geq 5n^2-25n\iff 25n\geq n^2\iff 25\geq n\]Which gives the desired conclusion.$\blacksquare$