Teorema de la amistad

Ahora, el teorema de la amistad dice: En cualquier grupo de seis personas, existen tres personas que son mutuamente conocidas o mutuamente desconocidas.

Sean las aristas coloreadas con los colores rojo o azul dependiendo de si las dos personas representadas por los vértices incidentes a la arista son mutuamente conocidos o desconocidos, respectivamente.

con los colores rojo o azul, no se puede evitar que exista un triángulo rojo, es decir, un triángulo que tenga sus tres lados de color rojo, lo que representa tres personas mutuamente extrañas o un triángulo azul, que representan tres personas mutuamente conocidas.

Según el principio del palomar, al menos tres aristas deben ser del mismo color, porque si hay menos de tres de un solo color, por ejemplo roja, entonces hay al menos tres que son de color azul.

Sean A, B, C, los otros vértices extremos de estas tres aristas, todas del mismo color, por ejemplo azul.

En 1930, en un trabajo titulado «On a Problem in Formal Logic» (Sobre un problema en lógica formal), Frank P. Ramsey demostró un teorema muy general, conocido en la actualidad como teorema de Ramsey en el que el teorema de la amistad es un caso particular.

Para demostrar esto, se colorea K5 de rojo y azul de forma que no contenga un triángulo cuyos lados sean todos del mismo color.

Por lo tanto, 6 es el mínimo número para el cual se puede dar por buena la conclusión del teorema de la amistad.