Teorema de la amistad

Los 78 grafos posibles de amigos-extraños con 6 vértices. En cada grafo, las aristas de color azul/rojo muestran la relación mutua de amigos/extraños.

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 teorema

Supongamos 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 conocido antes, en cuyo caso se les llamará mutuamente conocidos. Ahora, el teorema de la amistad nos dice que:

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

Conversión a grafos

Es conveniente 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 $K_n \,$. En el caso de un grafo de 3 vértices y en donde cada vértice es adyacente a los demás, se trata del grafo completo $K_3 \,$ o del ciclo de longitud 3: $C_3 \,$, comúnmente llamado triángulo.

Ahora tomemos un $K_6 \,$. 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 dos personas 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 las aristas de $K_6 \,$ 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 conocidos.

Prueba

Elijamos uno de los vértices P. Hay cinco aristas incidentes a P, cada una coloreada con el color rojo o azul. 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. Si alguna de las aristas AB, BC, CA es azul, entonces esta arista junto con las dos aristas incidentes a P forman los lados de un triángulo azul. Si ninguna de las aristas AB, BC, CA es azul, entonces las tres aristas son de color rojo y tenemos un triángulo rojo de vértices ABC.

Trabajo de Ramsey

La total simplicidad de este argumento, que produce con tanta fuerza una interesante conclusión, es lo que hace atractivo este teorema. 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. El teorema de Ramsey es la base en la que sostiene el área de la combinatoria conocida como teoría de Ramsey.

Ámbito del teorema de la amistad

Un coloreado de dos colores de K₅ sin un K₃ monocromo.

La conclusión del teorema de la amistad no se tiene en grupos de menos de seis personas. Para demostrar esto, se colorea K₅ de rojo y azul de forma que no contenga un triángulo cuyos lados sean todos del mismo color. Dibujamos K₅ como un pentágono que rodea una estrella y coloreamos de rojo los lados del pentágono y de azul los de la estrella. 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. En la teoría de Ramsey, esto se denota por:

$R(3,3: 2) = 6.\,$

Referencias

• V. Krishnamurthy. Culture, Excitement and Relevance of Mathematics, Wiley Eastern, 1990. ISBN 81-224-0272-0.

Véase también

• Coloración de grafos

Enlaces externos

• Bogomolny, Alexander. «Party Acquaintances» (en inglés). Interactive Mathematics Miscellany and Puzzles.