# combinatorics – There are \$2n\$ people on a social media platform. Prove there are at least \$5n\$ friends.

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?