(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?

(Source: Olimpiada de Mayo, 2012.)
So, how can this be solved (without considering lots of cases)?
Thank you.
 A: 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$.
