Problema del sábado 11 de enero. CONOCIDOS.

Bueno, ya es domingo, pero igual postearé un problema del sábado, perdonen el retraso. También, sé que este problema ya lo conoce Diego pero me pareció muy bonito. Además tiene varias soluciones muy distintas. Así que lo comparto.

Tenemos una gráfica finita de $2000$ vértices donde no puede haber más de una arista entre dos vértices y no hay aristas que vayan de un vértice a él mismo. Diré que dos vértices son amigos si son adyacentes. Diré que dos vértices son "conocidos" si tienen un amigo en común. La gráfica tiene un millón de aristas. Demuestra que hay al menos $999000$ parejas de conocidos.