There are $2n$ people on a social media platform. Prove there are at least $5n$ pairs of friends.

Question

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?

Answer 1

(This is just a hint.)

Hint: Split the 2n people into 2 groups A and B with $n$ people each.
Place some conditions on the groups so that the number of $A-B$ friends is at least 3n.
Then, the total number of friends is at least $5n$.

I've listed out the motivation / reasoning for the hint below. It is still not a full solution as it's missing the crux.

---

This was my approach, which felt quite natural.
It's conversational / train of thought / pursuing possible leads, as opposed to a properly written solution. My solution would be drastically different from what is presented.
Parts which I claim are "reasonable (?)" may not be reasonable to most other people, and could be considered magic / leaps of faith. It comes from experience / guessing / wishful thinking. If they didn't lead to a result, then I would have gone back to fiddle with them.

The first part motivates Aqua's claim that "the official solution is $5n$".
If you're willing to accept it (and not care about the construction), skip down to the next list of bullet points.
(I wanted a way to motivate it, not just assume it is true. Knowing that the answer is $5n$ is crucial to my process.)

• $n=1, 2$ would never satisfy the conditions. Let's ignore them.
• Observe that for $n = 3$, we must have the complete graph on 6 vertices. Trivially, any 3 people will have 3 friendships.
• To minimize the total number of friendships, while ensuring that there's a minimum number of friendships in some subset, it is reasonable (?) to expect that we have complete graphs of $a_1, a_2, \ldots a_k$ people with $ \sum a_i = 2n$. Then, given any $n$ people, if there are $b_i$ people in each graph with $ \sum b_i = n$, the number of friendships is $ \sum { b_i \choose 2 }$
• We want something like $ \sum {b_i \choose 2 } \geq k \sum (b_i + C) $ for some $k$ and constant $C$, with equality at $b_i = 3$. We also don't want equality to hold at $1, 2$ (and possibly 4), so it is reasonable (?) that it is a double root (Note: The other root could have been say 3.5).
• This gives us $(x-3)^2 \geq 0 \Leftrightarrow x(x-1) \geq 5x - 9$ as the actual inequality we want.
• For $3 \mid n$, then the idea is to split into groups of $a_i = 6$ people, and the minimum occurs when $b_i = 3$.
• We then have $ \sum_{i=1}^{2n/6} {b_i \choose 2} \geq \sum (5b_i - 9)/2 = 5n$.
• Might have to make slight adjustments for $ 3 \not \mid n$, but it's going to be around $ 5n \pm \epsilon$.

The second part shows that we need at least $5n$ people.

• Split the $2n$ into 2 groups, group A consisting of $n$ people and group B consisting of $n$ people.
• We know that group A has at least $n$ friends, and group B has at least $n$ friends amongst them, so we're wondering how many friends there are between A-B.
• Guessing that the answer is $5n$, it is reasonable (?) to show that there are at least $3n$ friends in A-B
• One possible approach is to show that the degree of each vertex from A to B is at least 3, so there are at least $3n$ friends.
• We know that the average degree of a vertex from B to B is 2.
• Hint: Perhaps there is a way to force the degree of a vertex from A to B to be strictly greater than any degree of the vertex from B to B. (Notice that we haven't placed any restrictions on how to form the groups as yet.)
• If that is true, then we have at least $n + 3n + n$ friends arising from A-A, A-B, B-B groups respectively.

Further cryptic hint: For Olympiad problems of a similar flavor, what characterization is often considered?

---

Solution to the hint:

Let $A$ be the group of $n$ people that minimizes the total number of friendships within $n$ people.
Let $B$ be the other $n$ people.

Claim 1: Given $a \in A$ and $b \in B$,

• If $a-b$ are not friends, then the number of friends in $A$ that $b$ has, is at least as many as the number of friends in $A$ that $a$ has.
• If $a-b$ are friends, then the number of friends in $A$ that $b$ has is strictly more than the number of friends in $A$ that $a$ has.

Proof: If the claim isn't true, swapping $a$ and $b$ results in fewer friendships within $A$, contradicting the minimality.

Claim 2 : Each person in $B$ is friends with at least 3 people in $A$.

Proof: Suppose not.
If some $b\in B$ is friends with 0 (resp. 1) people in $A$, then the number of friends in $A$ is at most 0 (resp. $n/2$). This contradicts the condition than $A$ contains at least $n$ friendships.
If some $b \in B$ is friends with 2 people in $A$, then everyone in $A$ has at most 2 friends in $A$. Since there are $n$ friendships, this means that everyone in $A$ has exactly 2 friends in $A$. However, then $b$, along with (either of) their friend in $A$ contradicts claim 1.

Corollary: The number of $A-B$ friendships is at least $3n$.

Answer 2

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

• At least $n$ edges between vertices of $V_1$.$\\[4pt]$
• At least $3n$ edges connecting vertices of $V_2$ with vertices of $V_1$.$\\[4pt]$
• At least $n$ edges between vertices of $V_2$.

for a total of at least $n+3n+n=5n\;$edges.

Answer 3

THM 1: Let $G$ be a graph on $2N$ vertices such that for every subset $S$ of $G$ of $N$ vertices, there are at least $N$ edges in $G$ with both endpoints in $S$. Then $G$ has at least $5N$ edges.

We now prove THM 1. Now let $S$ be a subset of $V(G)$ on $N$ vertices that satisfies the following: For all other subsets $S'$ of $G$ with $N$ vertices, the number of edges in $G[S']$, is at least as large as the number of edges in $G[S]$.

We make the following claim:

Claim 1: Every vertex $y$ in $V(G)\setminus S$ has at least 3 neighbors in $S$.

Proof: Suppose otherwise. Let $y$ be a vertex with 2 or fewer neighbors in $S$. We consider 2 cases:

Case 1: $y$ has at least one neighbor in $G[S]$, and $G[S]$ has no vertices of degree-3 or higher. Then every vertex in $G[S]$ must have degree no more than 2, and so the hypothesis of THM 1 implies every vertex in $G[S]$ has degree 2 and so $G[S]$ has exactly $N$ edges. So $G[S+\{y\}]$ has no more than $N+2$ vertices and at least 1 vertex $v$ of degree 3 in $G[S+\{y\}]$, namely, $v$ can be any one of $y$'s neighbors in $S$. So $G[S +\{y\} - \{v\}]$ has no more than $N+2-3<N$ vertices which contradicts the hypothesis of THM 1.

Case 2: $G[S]$ has at least one vertex of degree 3, or $y$ has no neighbors in $S$. In either case, there is a vertex $v \in S$ such that
$y$ has fewer neighbors in $S$ than $v$ does. So $(S-\{v\})+\{y\}$ has $N$ vertices yet $G[(S-\{v\})+\{y\}]$ has fewer neighbors than $G[S]$ does, which contradicts the definition of $S$.

Note that Cases 1 and 2 cover all possibilities. So Claim 1 holds. $\surd$

So let us now use this to lower-bound the number of edges in $G$. Let us set $T=V(G)\setminus S$. Then $T$ and $S$ are disjoint and each have exactly $N$ vertices and partition $\Omega \doteq V(G)$.

Then by Claim 1 there are $3N$ edges between $S$ and $T$, and by the hypthesis, there are at least $N$ edges with both endpoints in $S$, and there are are at least $N$ edges with both endpoints in $T$. Which gives at least $3N+N+N=5N$ edges total. And thus THM 1 follows. $\surd$

---

This bound is tight for $N$ a multiple of 3, and is within $O(1)$ edges of being tight for other $N$. Take the graph $G$ consisting of $\frac{N}{3}$ cliques with precisely 6 vertices in each clique for $N \pmod 3 =0$, and of $\lfloor \frac{N}{3} \rfloor$ cliques, all but the last having exactly 6 vertices and the rest having the remaining 8 or 10 vertices, for $N \pmod 3 =1,2$. This graph satisfies the conditions of the hypothesis of THM 1.