théorème de l'amitié

Imaginez sept personnes. Chaque fois que vous en choisissez deux, elles ont une seule amie commune dans le groupe. Cette contrainte paraît locale, puisqu'elle ne concerne qu'une paire à la fois. Pourtant, elle force une organisation globale : une personne est amie avec les six autres.

Autour de cette personne centrale, les six autres se rangent par couples. Chaque couple et le centre forment un triangle. L'ensemble ressemble ainsi aux pales d'un moulin à vent qui se rejoignent au même moyeu.

Le théorème de l'amitié porte sur un graphe fini non vide : les sommets représentent les personnes et une arête relie deux personnes amies. La relation est supposée symétrique, donc les arêtes ne sont pas orientées. Pour toute paire de sommets distincts, il doit exister exactement un sommet adjacent aux deux, appelé leur voisin commun.

Sous cette hypothèse, la finitude permet d'abord de montrer qu'un sommet est adjacent à tous les autres. Dans le vocabulaire social, c'est le « politicien ». Une fois ce centre obtenu, chaque autre sommet possède exactement un voisin commun avec lui : cet unique voisin est un autre sommet extérieur. Les sommets extérieurs se regroupent donc en paires reliées ; aucun ne peut appartenir à deux paires, sinon lui et le centre auraient plusieurs voisins communs. Chaque paire forme ainsi un triangle avec le politicien. Le graphe est donc un moulin à vent, c'est-à-dire une collection de triangles ayant pour unique sommet commun leur centre.

S'il y a k triangles, le graphe compte un sommet central et deux sommets par triangle, soit $n=2k+1n=2k+1$ sommets. Le nombre n de personnes est donc impair. La finitude est une hypothèse essentielle : la conclusion n'est pas valable pour tous les graphes infinis. La première démonstration rigoureuse est due à Paul Erdős, Alfréd Rényi et Vera Sós.

Soit un graphe fini non orienté et non vide. Si toute paire de sommets distincts possède exactement un voisin commun, alors un sommet est adjacent à tous les autres. Le graphe est une réunion de triangles qui ne partagent que ce sommet central. En notant k le nombre de triangles et n le nombre total de sommets, on obtient $n=2k+1n=2k+1$ ; n est donc impair.

Le théorème s'applique à un graphe fini dont les arêtes traduisent une relation symétrique. Il faut contrôler toutes les paires de sommets distincts, qu'elles soient elles-mêmes reliées ou non. Pour chacune, le nombre de voisins communs doit être exactement égal à un.

Si deux personnes ont deux amis communs, l'hypothèse échoue déjà et aucune conclusion sur un politicien ne suit du théorème. De même, si Alice déclare Bob comme ami sans réciprocité, le modèle devient un graphe orienté : il faut alors préciser les liens entrants et sortants et employer un résultat adapté. Enfin, un réseau infini sort du domaine du théorème, même si sa règle locale semble identique.

Prenons sept personnes : P, A₁, A₂, B₁, B₂, C₁ et C₂. Le schéma représente trois triangles ayant P pour sommet commun.

Données.
P est ami avec les six autres personnes.
Les trois couples A₁–A₂, B₁–B₂ et C₁–C₂ sont amis.
Il n'existe aucune autre relation d'amitié.

Étape 1. Deux membres d'un même couple, comme A₁ et A₂, ont pour unique ami commun P.

Étape 2. P et un sommet extérieur, par exemple A₁, ont pour unique ami commun l'autre membre du couple, ici A₂.

Étape 3. Deux sommets appartenant à des couples différents, comme A₁ et B₁, ont P pour unique ami commun. Ces trois cas couvrent toutes les paires possibles.

Contrôle. P est bien ami avec toutes les autres personnes. Avec k = 3 triangles, le total vaut $n=2\times 3+1=7n=2\backslash times3+1=7$, un nombre impair.

Dans un exercice, on traduit d'abord les personnes par des sommets et les amitiés réciproques par des arêtes. On compte ensuite les voisins communs de chaque paire. Si le compte vaut toujours un et si le graphe est fini, le théorème donne immédiatement un sommet universel.

Pour construire un exemple, on choisit un centre, puis on ajoute des couples indépendants reliés au centre. Cette construction en triangles garantit la propriété et fournit toujours un nombre impair de sommets.

Pour des données sociales réelles, la réciprocité et l'exhaustivité des liens doivent être vérifiées avant toute application. Si les déclarations sont orientées ou incomplètes, une analyse descriptive du réseau est préférable : le théorème ne corrige pas les données manquantes.

Avec le paradoxe de l'amitié. Ce paradoxe compare le nombre d'amis d'une personne à celui de ses amis. Le théorème étudié impose au contraire exactement un ami commun à chaque paire. Un réseau peut illustrer le paradoxe sans former un moulin à vent.

Avec un simple sommet de degré maximal. Être la personne la plus connectée ne suffit pas. Le « politicien » est adjacent à tous les autres sommets ; dans l'exemple à sept personnes, son degré vaut exactement six.

Le mot « exactement » est décisif. Zéro voisin commun ou deux voisins communs pour une seule paire suffit à bloquer le théorème. Il faut reprendre le comptage paire par paire au lieu de conclure à partir d'une moyenne.

La finitude ne se retire pas. La règle locale ne force pas la même conclusion dans tous les graphes infinis. Face à un réseau infini, il faut établir séparément l'existence d'un sommet universel ; le théorème de l'amitié fini ne la fournit pas.

Le plus petit cas non trivial compte trois sommets. Un seul triangle satisfait la propriété et chacun de ses sommets est adjacent aux deux autres. Le sommet universel n'est alors pas unique. À partir de deux triangles partageant leur centre, seul ce centre est universel.

L'impair est une conséquence, pas un critère suffisant. Un graphe à sept sommets quelconque ne vérifie pas nécessairement l'hypothèse. Il faut retrouver la structure complète en triangles partageant un même centre.

La propriété locale sur les voisins communs détermine ici tout le graphe. Cette rigidité invite à étudier d'autres familles où une contrainte imposée à chaque paire de sommets force une structure globale.

Balades dans le graphe divisoriel montre un autre graphe défini par une relation précise et développe la lecture de ses chemins.