Princípio da Casa dos Pombos

(EUA)  Em uma festa há n pessoas. Prove que existem duas pessoas tais que, das n-2 pessoas restantes é possível achar [latex]\left \lfloor \frac{n}{2}\right \rfloor-1[/latex] onde cada uma delas conhece ou não conhecem ambas.

É teoria dos grafos. Vou considerar como dois pontos encontrados A e B

Considere o número de pares (X, {Y, Z}), onde X, Y, Z são pontos distintos, de modo que X é unido a apenas um de Y, Z. Se X é unido a apenas k pontos, então há apenas [latex] k (n - 1 - k) \leq \frac{(n - 1)^2}{4} [/latex] desses pares (X, {Y, Z}). Portanto, no total, há no máximo [latex] \frac{n (n - 1)^2}{4}[/latex] desses pares. Mas há [latex] \frac{n (n - 1) }{2} [/latex] possíveis {Y, Z}. Portanto, devemos ser capazes de encontrar um deles {A, B} que pertença a no máximo [latex] \frac{(n - 1)}{2}[/latex]  desses pares. Portanto, há pelo menos [latex] n - 2 - [\frac{n - 1}{ 2}] = [\frac{n}{2}] - 1[/latex]  pontos X que são unidos a ambos A e B ou a nenhum de A e B.