Teorema de l'amistat

Els 78 grafos possibles d'amics-estranys en 6 vèrtiços. En cada grafo, les arestes de color blau/roig mostren la relació mútua d'amics/estranys.

La teorema d'amics i estranys o teorema de l'amistat és un teorema en el camp matemàtic cridat teoria de Ramsey.

Formulació de la teorema

Suponga's que en una festa hi ha 6 persones. Considere's a dos qualsevol d'elles. Pot ser que es reunixquen per primera volta, en el cas del qual són mútuament desconegudes, o pot ser que s'hagen conegut abans, en el cas del qual se'ls cridarà mútuament conegudes. Ara, la teorema de l'amistat diu:

En qualsevol grup de sis persones, existixen tres persones que són mútuament conegudes o mútuament desconegudes.

Conversió a grafos

És convenient expressar este problema usant el llenguage de teoria de grafos.

Suponga's que un grafo té 6 vèrtiços i cada parell de vèrtiços està unit per una aresta. Este grafo es diu grafo complet. Un grafo complet de n vèrtiços es denota per $K_n$. En el cas d'un grafo de 3 vèrtiços i en a on cada vèrtiç és adjacent als demés, es tracta del grafo complet $K_3$ o del cicle de llongitut 3: $C_3$, comunament cridat triàngul.

Ara prenga's un $K_6$. Este grafo complet té 15 arestes en total. Siguen les 6 persones de la festa representades pels 6 vèrtiços. Siguen les arestes coloreadas en els colors roig o blau depenent de si les dos persones representades pels vèrtiços incidents a l'aresta són mútuament coneguts o desconeguts, respectivament. La teorema de l'amistat afirma ara:

No importa cóm s'ha coloreado les arestes de $K_6$ en els colors roig o blau, no es pot evitar que existixca un triàngul roig, és dir, un triàngul que tinga els seus tres costats de color roig, lo que representa tres persones mútuament estranyes o un triàngul blau, que representen tres persones mútuament conegudes.

Referències

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

Vore també

• Coloració de grafos