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 $${2n\choose n} \cdot n \leq \varepsilon \cdot {2n-2\choose n-2} \implies \varepsilon\geq {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?
Best Answer
Let $G=(V,E)$ be a graph with $2n$ vertices such that for any subset $S\subset V$ with $|S|=n$, the induced subgraph $G[S]$ has at least $n$ edges.
Our goal is to show $|E|\ge 5n$.
Here's how I would do it . . .
Of all $n$-element subsets of $V$, choose one, $V_1$ say, for which $|E_1|$ is least, where $E_1$ is the set of edges of the subgraph $G_1=G[V_1]=(V_1,E_1)$.
Let $V_2=V{\,{\large{\setminus}}}V_1$.
Claim:$\;$For each $v_2\in V_2$, there are at least $3$ edges connecting $v_2$ with elements of $V_1$.
Proof:
Consider two cases . . .
Case $1$:$\;$In $G_1$, there is at least one vertex of degree at least $3$.
Let $v_1$ be a vertex having degree at least $3$ in $G_1$.
Let $v_2\in V_2$ be arbitrary, and let $H=G_1-v_1+v_2$.
Since $H$ has $n$ vertices, then by the minimality of $|E_1|$, to compensate for the removal of $v_1$, it follows that $v_2$ must have degree at least $3$ in $H$.
It follows that the claim holds for case $1$.
Case $2$:$\;$In $G_1$, there are no vertices of degree at least $3$.
Then in $G_1$, the sum of the degrees is at most $2n$.
But since $|E_1|\ge n$, the sum of the degrees in $G_1$ is at least $2n$, hence the sum of the degrees in $G_1$ must be exactly $2n$.
Then since there are no vertices of degree at least $3$ in $G_1$, it follows that in $G_1$, all vertices have degree exactly $2$.
Let $v_1\in V_1$ be arbitrary.
Let $v_2\in V_2$ be arbitrary, and let $H=G_1-v_1+v_2$.
Since $H$ has $n$ vertices, then by the minimality of $|E_1|$, to compensate for the removal of $v_1$, it follows that $v_2$ must have degree at least $2$ in $H$. Hence there are at least $2$ edges connecting $v_2$ with elements of $V_1-\{v_1\}$. In particular, if $v_1\in V_1$ is adjacent to $v_2$, then since there are at least $2$ edges connecting $v_2$ with elements of $V_1-\{v_1\}$, it follows that there are at least $3$ edges connecting $v_2$ with elements of $V_1$.
Thus the claim also holds for case $2$, so the claim is proved.
Hence $G$ has
for a total of at least $n+3n+n=5n\;$edges.