théorème de l’amitié

COMBINATOIRE

Il s’agit d’un théorème en théorie des graphes, dont un énoncé peut être :
« Dans un groupe de n personnes, si deux personnes quelconques ont un et un seul ami commun qui fait partie du groupe, alors l’une des personnes (le politicien) est amie de toutes les autres et n est impair. »

On suppose tacitement que l’amitié est réciproque et on traduit en théorie des graphes :
« Soit G un graphe fini dans lequel deux sommets ont toujours exactement un voisin commun. Alors il existe un sommet adjacent à tous les autres. »
Ces graphes sont en forme de moulin à vent.
La première démonstration est due à Paul Erdös , Alfred Renyi et Vera Sös .
L’énoncé ne se généralise pas aux graphes infinis.