There are $2n$ people on a social media platform, where any pair of them may or may not be

friends. For any group of $n$ people, there are at least $n$ pairs of them that are friends. What

is the least number of friendships, that is, the least number of pairs of people that are friends, that

must be among the $2n$ people?

This a problem from last year Canadian national competition. Offical solution is $5n$.

Here is what I did: For every $n$ vertices we have $n$ edges so $${2nchoose n} cdot n leq varepsilon cdot {2n-2choose n-2} implies varepsilongeq {2n(2n-1)over n-1} $$

So, by this to naive method we get: $$varepsilon geq 4n+3$$

I also wonder if this is doable with the probabilistic method?