# (Olympiad) Minimum number of pairs of friends.

I gave up, my approaches didn't work (induction, pigeon-hole, parity; though obviously there's a good chance I didn't use them cleverly):

In a group of 12 people, every pair of them has a common friend (in the same group). It is understood that friendship is a non-reflexive (a person is not a friend of herself), symmetric, not necessarily transitive relation (so this can be represented by a simple graph). What is the minimum number of pairs of friends among them?

So, how can this be solved (without considering lots of cases)?

Thank you.

-
non-transitive relation : A ~ B and B ~ C then A is not a friend of C Right ? What is the non-reflexive condition ? – HK Lee Nov 9 '12 at 13:45
@user37116 I edited it. Thank you. – Weltschmerz Nov 9 '12 at 13:49
I believe the answer is 21. Do you know the answer? – P.. Nov 9 '12 at 13:53
@Henry Henry, Pambos: draw one in the center and the other 11 around. Make the one in the center friends with everybody else. Draw a polygon with the other 11, then remove as many sides of that polygon as you can. You get 17 pairs of friends. – Weltschmerz Nov 9 '12 at 14:06
Weltschmerz: Indeed, this is a friendship graph with 11 vertices and 15 friendships, plus 1 more vertex with 2 friendships of which one is to the friendliest vertex – Henry Nov 9 '12 at 14:19

OK, the answer is $17$. The solution doesn't involve any case analysis, but it is far from elegant.

For an example with $17$ pairs of friends, see the comments to the question. I will only prove that the number of pairs of friends is always at least $17$.

We can describe the situation by an undirected graph $G=(V, E)$ with $|V|=12$ vertices. Choose an arbitrary vertex $a \in V$. Let $A$ be the set of all the vertices that are connected to $a$. Note that the diameter of $G$ is at most $2$, which means that every vertex $b$ from the set $V\setminus (A \cup \{a\})$ is connected to some vertex $c$ from $A$.

Now we will split $V\setminus(A\cup\{a\})$ into two subsets. Let $B$ be the set of all vertices from $V\setminus(A\cup\{a\})$ that don't have any neighbours in $V\setminus(A\cup\{a\})$, and let $C=V\setminus(A\cup B \cup\{a\})$.

For any two subsets $X$ and $Y$ of $V$, let us denote by $n(X, Y)$ the number of edges having one end in $X$ and the other in $Y$. Due to the construction of $a, A, B$ and $C$ we have: $$n(a, B) = n(a, C) = n(B, C) = n(B, B) = 0.$$ Therefore, the total number of edges in the graph is $$|E| = n(a, A) + n(B, A) + n(C, A) + n(A, A) + n(C, C).$$ Now we will make some estimates on the individual terms. It is clear that $n(a, A) = |A|$ and that $n(C, A) \geqslant |C|$.

To make an estimate on $n(B, A)$, let us consider any vertex $b \in B$. As we know, it has at least one neighbour $x$ in $A$. Also, $b$ and $x$ have a common neighbour $y$. $y$ cannot be $a$, because $b$ isn't connected to $a$. $y$ cannot belong to $B \cup C$ by definition of $B$. Therefore, $y \in A$. So, every vertex $b \in B$ has at least $2$ neighbours in $A$, and $n(B, A) \geqslant 2 |B|$.

For an estimate on $n(A, A)$, consider vertex $a$ and any $x \in A$. They have a common neighbour $y$. Since $y$ is connected to $a$, $y \in A$. So, every vertex in $A$ has a neighbour in $A$. One can easily see then that $n(A, A) \geqslant |A|/2$.

Finally, let's make an estimate on $n(C, C)$. By the construction of $C$, every vertex of $C$ has a neighbour in $C$, therefore $n(C, C) \geqslant |C|/2$.

Putting all the estimates together, we get $$|E| \geqslant |A| + 2|B| + |C| + \frac{1}{2}|A| + \frac{1}{2}|C| \geqslant \frac{3}{2}(|A| + |B| + |C|) = \frac{3}{2} \cdot 11 = 16\frac{1}{2}.$$ And so we have it: $|E| \geqslant 17$.

-
BTW, I'm not sure about using the word "estimate" here. Maybe "bound" is better. In Russian the word for "estimate" is also frequently used to mean "bound". Is it the same in English? – Dan Shved Nov 9 '12 at 15:25
Your solution is fantastic. What disturbs me is the fact that the other four problems in that contest (for classes 6-7) were really easy. – Weltschmerz Nov 9 '12 at 16:18
What's the age of students of classes 6-7? By the way, what country is that? I would guess Brazil or Argentina from the few words that I saw on the website. – Dan Shved Nov 9 '12 at 16:30
I think it's classes 6-8 actually. The competition is for Latin American countries. Ages vary widely. 10-14 could be. – Weltschmerz Nov 9 '12 at 16:33
Hm. Well, I guess a well-trained 14 year old could find a solution similar to this one. Kids can be extremely scary ) But if the other problems are easy, then it does look suspicious. Maybe we are all missing a short simple idea. – Dan Shved Nov 9 '12 at 16:46