Teoria de la amistad

Teorema de la amistad

1

Teorema de la amistad
El teorema de amigos y extraños o teorema de la amistad es un teorema en el campo matemático llamado teoría de Ramsey.

Formulación del teoremaSupongamos que en una fiesta hay 6 personas. Consideremos a cualquiera dos de ellos. Puede ser que se reúnen por primera vez, en cuyo caso son mutuamente extraños, o puede ser que se hayan conocidoantes, en cuyo caso se les llamará mutuamente conocidos. Ahora, el teorema de la amistad nos dice que:
Los 78 grafos posibles de amigos-extraños con 6 vértices. En cada grafo, las aristas de colorazul/rojo muestran la relación mutua de amigos/extraños.

En cualquier grupo de seis personas, existen tres personas que son mutuamente conocidas o mutuamente desconocidas.

Conversión a grafos
Esconveniente expresar este problema usando el lenguaje de teoría de grafos. Supongamos que un grafo tiene 6 vértices y cada par de vértices está unido por una arista. Este grafo se llama grafo completo.Un grafo completo de n vértices se denota por . En el caso de un grafo de 3 vértices y en donde cada vértice es adyacente a los demas, se trata del grafo completo llamado triángulo. Ahora tomemos un. Este grafo completo tiene 15 aristas en total. Sean las 6 personas de la fiesta representadas por los 6 vértices. Sean las aristas coloreadas con los colores rojo o azul dependiendo de si las dospersonas representadas por los vértices incidentes a la arista son mutuamente conocidos o desconocidos, respectivamente. El teorema de la Amistad afirma ahora:
No importa cómo se ha coloreado lasaristas de con los colores rojo o azul, no se puede evitar que exista un triángulo rojo, es

o del ciclo de longitud 3:

, comúnmente

decir, un triángulo que tenga sus tres lados de color rojo, loque representa tres personas mutuamente extrañas o un triángulo azul, que representan tres personas mutuamente conocidos.

Prueba
Elijamos uno de los vértices P. Hay cinco aristas incidentes a P,...