Bien, la respuesta es $17$ . La solución no implica ningún análisis de caso, pero está lejos de ser elegante.
Para un ejemplo con $17$ pares de amigos, ver los comentarios a la pregunta. Sólo probaré que el número de parejas de amigos es siempre al menos $17$ .
Podemos describir la situación por un gráfico no dirigido $G=(V, E)$ con $|V|=12$ vértices. Elija un vértice arbitrario $a \in V$ . Deje que $A$ ser el conjunto de todos los vértices que están conectados a $a$ . Tenga en cuenta que el diámetro de $G$ es como mucho $2$ lo que significa que cada vértice $b$ del set $V \setminus (A \cup \{a\})$ está conectado a algún vértice $c$ de $A$ .
Ahora nos dividiremos $V \setminus (A \cup\ {a\})$ en dos subconjuntos. Que $B$ ser el conjunto de todos los vértices de $V \setminus (A \cup\ {a\})$ que no tienen vecinos en $V \setminus (A \cup\ {a\})$ y dejar que $C=V \setminus (A \cup B \cup\ {a\})$ .
Para dos subconjuntos cualesquiera $X$ y $Y$ de $V$ denotémoslo con $n(X, Y)$ el número de bordes que tienen un extremo en $X$ y el otro en $Y$ . Debido a la construcción de $a, A, B$ y $C$ que tenemos: $$ n(a, B) = n(a, C) = n(B, C) = n(B, B) = 0. $$ Por lo tanto, el número total de bordes en el gráfico es $$ |E| = n(a, A) + n(B, A) + n(C, A) + n(A, A) + n(C, C). $$ Ahora haremos algunas estimaciones en los términos individuales. Está claro que $n(a, A) = |A|$ y que $n(C, A) \geqslant |C|$ .
Para hacer una estimación sobre $n(B, A)$ Consideremos cualquier vértice $b \in B$ . Como sabemos, tiene al menos un vecino $x$ en $A$ . También, $b$ y $x$ tienen un vecino común $y$ . $y$ no puede ser $a$ porque $b$ no está conectado a $a$ . $y$ no puede pertenecer a $B \cup C$ por definición de $B$ . Por lo tanto, $y \in A$ . Así que, cada vértice $b \in B$ tiene al menos $2$ vecinos en $A$ y $n(B, A) \geqslant 2 |B|$ .
Para una estimación de $n(A, A)$ considerar el vértice $a$ y cualquier $x \in A$ . Tienen un vecino común $y$ . Desde $y$ está conectado a $a$ , $y \in A$ . Así que, cada vértice en $A$ tiene un vecino en $A$ . Uno puede ver fácilmente entonces que $n(A, A) \geqslant |A|/2$ .
Finalmente, hagamos una estimación de $n(C, C)$ . Por la construcción de $C$ cada vértice de $C$ tiene un vecino en $C$ Por lo tanto $n(C, C) \geqslant |C|/2$ .
Poniendo todas las estimaciones juntas, obtenemos $$ |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}. $$ Y así lo tenemos: $|E| \geqslant 17$ .
